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