首页 > 笔记 > Matrix-Tree定理总结

Matrix-Tree定理总结

花了一节课看行列式的定义、Matrix-Tree定理证明后,发现结论就一句话:

搞一个矩阵为某图的度数矩阵减去邻接矩阵,把它高斯消元成上三角,把前n-1行的对角线乘起来就是这个图的生成树数量。

度数矩阵:$a[i][i]$为$i$度数。
邻接矩阵:$a[i][j]$为$i,j$间的边数。

证明啥的懒得写,比较正常的版本应该是:

一个图的生成树数量为其的Kirchhoff矩阵任何一个$n-1$阶主子式的行列式的绝对值。

SPOJ Highways

裸题、注意:高斯消元系数为0直接return

轮状病毒

需要用高精小数。。调了半天放弃了。

50分

正解是高精的递推


如果你觉的这篇文章不错,分享给朋友吧!

打开微信“扫一扫”,打开网页后点击屏幕右上角分享按钮

×