欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

最小生成生成树计数

程序员文章站 2024-03-19 22:14:46
...
    对于生成树计数问题,解决的方法一般有矩阵树定理+kruscal,或者只用kruscal。我们可以发现,解决问题的关键在于一个定理:
    最小生成树中边权相同的联通块,在任意一个生成树中连通性并不改变。
    有了这个定理,我们对图进行相同权值边的统计,然后用2^n或矩阵树定理来求解
这个联通块内的生成树个数。
    最后用乘法原理解决问题。
相关标签: 算法随笔