[BZOJ 4031] [HEOI 2015] 小Z的房间

Kirchhoff's theorem or Kirchhoff's matrix tree theorem

  1. G的度数矩阵DG是一个n*n的矩阵,并且满足:当i≠j时,Di,j=0;当i=j时,Di,j等于Vi的度数。
  2. G的邻接矩阵AG也是一个n*n的矩阵,并且满足:如果ViVj之间有边直接相连,则Ai,j=1,否则为0。

定义G的 Kirchhoff 矩阵CGCG=DGAG

Matrix-Tree 定理:G的所有不同的生成树的个数等于其 Kirchhoff 矩阵 CG任何一个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的房间