(Matrix-tree) 定理用来解决一类生成树计数问题，以下前置知识内容均是先基于无向无权图来介绍的。有关代数余子式的部分不是很明白，如果有错误还请指出……
部分内容参考至：(Blog\_1) & (Blog\_2)。
(Laplacian) 矩阵
定义：
在 (n) 个点的无向图中：
度数矩阵 (D) 即为一个 (n*n) 的矩阵，定义为 (D[i][i]=i) 号点的度数，(D[i][j]=0) ((i
e j))。
邻接矩阵 (A) 即为一个 (n*n) 的矩阵，定义为 (A[i][j]=i, j) 之间的边数。
则其拉普拉斯矩阵其实就是图的度数矩阵减去邻接矩阵，即 (L=D-A)。
对此，可以直接的总结出 (laplacian) 矩阵中各元素的值为：
矩阵行列式性质及求法
行列式：
在一个 (n*n) 的矩阵中，选出 (n) 个互相不同行不同列的数，其乘积的值冠以符号 ((-1)^t)，得到式子：((-1)^t · a_{1,p_1} · a_{2,p_2} · a_{3,p_3} · ... · a_{n,p_n})；
其中，(p) 为自然数 (1~n) 的一个排列，(t) 为这个排列的逆序对数，可知形同上式的项共有 (n!) 个。所有这些项的代数和称为矩阵的 (n) 阶行列式，简记为 (det(i,j))，其中数 (i,j) 为行列式 (D) 的 ((i, j)) 元。
也可以理解为矩阵 (A) 任意一行(列)的各元素与其对应的代数余子式乘积之和。
行列式的性质：
· 互换矩阵的两行(列)，行列式变号
· 矩阵有两行(列)成比例(比例系数 (k))，则行列式的值为 (0)
· 矩阵的某一行(列)中的所有元素都乘以同一个数 (k)，新行列式的值等于原行列式的值乘上数 (k)
· 把矩阵的某一行(列)加上另一行(列)的 (k) 倍，则行列式的值不变
行列式的求法：
按照定义来求行列式的复杂度实在是太高了，考虑一些更快的方法。
给出一个上三角/下三角矩阵，其行列式的值为对角线的乘积，因为只有 (p={1,2,3...n}) 时，乘积项中才没有 (0) 出现。
采用高斯消元的方法，把矩阵消为一个上三角矩阵后，然后求出对角线的积，便是该矩阵的行列式的值。
高斯消元
高斯消元：
上面提到了高斯消元，我之前也学习过，不过忘记的差不多了……（之前的博客）
这里简单放一下，顺便做个复习补充。
模意义下的高斯消元：
如果要求的矩阵不允许出现实数，且需要取模，则采用辗转相除的高斯消元法，至于这个辗转相除，复杂度高不了多少。
众所周知 高斯消元需要做除法，而模意义下是没有除法拿来做的。计算高斯消元的时候，如果模数是质数，那么除法逆元可以直接用费马小定理解决。否则我们对于矩阵中的两行，不断地把主元较大的那一行减去主元较小的那一行，最终一定有一行主元为 (0)，也就完成了消元。
发现以上思想是更相减损术的思想，效率太低，就可以拿辗转相除代替。
需要注意的是，我们在做的时候会交换行，而由行列式的性质，我们需要统计一下交换的次数：如果次数为奇数，那么最后的答案还要乘上模意义下的 (-1)。
inline void Gaussian() {
for(int i = 1; i <= n; ++i)
for(int j = i + 1; j <= n; ++j) while( kir[j][i] ) {
int tmp = kir[i][i] / kir[j][i];
for(int k = i; k <= n; ++k) {
kir[i][k] = (kir[i][k] - tmp * kir[j][k] % mod + mod) % mod;
swap(kir[i][k], kir[j][k]);
}
ans = (mod - ans) % mod;
}
}
(Matrix-tree) 定理
定理内容：
应用中，无向图的生成树个数就等于这副图的 (laplacian) 矩阵的任意一个代数余子式值，也可以理解为 (laplacian) 矩阵一个余子式的行列式的值。
余子式和代数余子式：
(M_{i,j}) 表示矩阵的一个余子式，指去掉元素 (a_{i,j}) 所在的行和列后剩余的矩阵部分。
(C_{i,j}) 表示矩阵的一个代数余子式，定义为 (C_{i,j}=(-1)^{i+j}M_{i,j})。
定理总结：
· 存在性质：(laplacian) 矩阵的任意一个代数余子式值都相同。
· 求得 (laplacian) 矩阵后，取一个余子式用高斯消元得到新矩阵的上三角矩阵，对角线乘积的绝对值就是生成树个数。
定理推广：
对于消去自环影响的有向图，也可以求以 (i) 为根的外向树/内向树个数，此时的 (laplacian) 矩阵定义为：
例题及拓展性质
([SDOI2014]) 重建：
给一个图，每条边有出现概率，求这个图恰好为一棵树的概率。
考虑 (laplacian) 矩阵的意义：之所以能够进行生成树计数是对于其关联矩阵在计数 (n−1) 条边的集合时，当 (n−1) 条边中存在环就会产生线性组合而导致行列式为零，否则恰好对角线上均为关联矩阵中所赋的值，使得 (det(B_{i,j})^2) 就为 (1)（有关这一部分的理解请看文章首部给出的 (Blog\_2) 链接）。
因此可以令邻接矩阵中存下边权，以计数生成树中边权的乘积。
这道题告诉我们：邻接矩阵中的的权可以不是 (1)，而是其他权值，比如概率。
了解了这个之后，就直接放一篇别人的题解 (Blog\_3) 在这里好了。
#include <cmath>
#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define scnaf scanf
const double eps = 1e-8;
const int maxn = 50 + 5;
int n; double p[maxn][maxn], tmp, ans;
inline double Abs(double x) { return x < 0 ? -x : x; }
inline void Gaussian() {
for(int maxx = 1, i = 1; i < n; maxx = ++i) {
for(int j = i + 1; j < n; ++j) if( Abs(p[j][i]) > Abs(p[maxx][i]) ) maxx = j;
if( maxx != i ) for(int j = 1; j < n; ++j) swap(p[i][j], p[maxx][j]);
for(int k = i + 1; k < n; ++k) {
double mul = p[k][i] / p[i][i];
for(int j = i; j < n; ++j) p[k][j] = p[k][j] - p[i][j] * mul;
}
if( Abs(p[i][i]) < eps ) { ans = 0.0; return ; }
}
for(int i = 1; i < n; ++i) ans = ans * p[i][i];
}
int main(int argc, char const *argv[])
{
freopen("nanjolno.in", "r", stdin);
freopen("nanjolno.out", "w", stdout);
scnaf("%d", &n), tmp = 1.0, ans = 1.0;
for(int i = 1; i <= n; ++i) for(int j = 1; j <= n; ++j) {
scnaf("%lf", &p[i][j]);
if( i < j ) tmp = tmp * (1.0 - p[i][j]);
p[i][j] = p[i][j] < eps ? eps : min(p[i][j], 1.0 - eps);
p[i][j] = p[i][j] / (1.0 - p[i][j]);
}
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j) if( i != j ) p[i][i] = p[i][i] - p[i][j];
Gaussian(), printf("%.6lf
", Abs(ans * tmp));
fclose(stdin), fclose(stdout);
return 0;
}
其他题目：
([SHOI2016]) 黑暗前的幻想乡
([HEOI2015]) 小Z的房间
([FJOI2007]) 轮状病毒
([JSOI2008]) 最小生成树计数
林下带残梦，叶飞时忽惊。