矩阵树定理 – 泉州一中信息学

Kirchhoff's theorem or Kirchhoff's matrix tree theorem

G的度数矩阵 $D_{G}$ 是一个n*n的矩阵，并且满足：当i≠j时, $D_{i, j}$ =0；当i=j时， $D_{i, j}$ 等于 $V_{i}$ 的度数。

G的邻接矩阵 $A_{G}$ 也是一个n*n的矩阵，并且满足：如果 $V_{i}$ 、 $V_{j}$ 之间有边直接相连，则 $A_{i, j}$ =1，否则为0。

定义G的 Kirchhoff 矩阵 $C_{G}$ 为 $C_{G} = D_{G} - A_{G}$ 。

Matrix-Tree 定理：G的所有不同的生成树的个数等于其 Kirchhoff 矩阵 $C_{G}$ 任何一个n-1阶主子式（去掉第行第i列的新矩阵）的行列式的绝对值。

运用高斯消元计算行列式绝对值。高斯消元过程中除法运用辗转相消实现。

Reference:

https://www.cnblogs.com/wuyuhan/p/5238652.html

https://www.cnblogs.com/GerynOhenz/p/4450417.html

http://blog.csdn.net/u010182633/article/details/45225179

代码如下：

继续阅读[BZOJ 4031] [HEOI 2015] 小Z的房间