P6178 Matrix-Tree 定理 题解
_HCl_
·
·
题解
小蒟蒻第一次写模板题解，有错误请见谅。
P6178 题解（矩阵树定理）
题意简述
给定一张无向/有向的带权图，定义一颗生成树的权值为其所有边权的乘积，求该图所有生成树的权值和。
特别地，对于有向图，生成树为以 1 为根的外向树。
定理介绍
矩阵树定理可以求出无权图的生成树个数。其中无权图允许重边但不允许自环。
先介绍三个矩阵，度矩阵，邻接矩阵和 Laplace 矩阵。
对于无向图，度矩阵记录每一个节点的度。
D_{i,j}=\begin{cases}deg_i&i=j\\0&i\neq j\end{cases}
对于有向图，有出度矩阵 D^{out} 和入度矩阵 D^{in}。也就是将上式中的度数换成出度/入度。
邻接矩阵记录每两个点之间的重边数量。用 e_{i,j} 表示从 i 到 j 的重边数量。
A_{i,j}=e_{i,j}
对于无向图：
L=D-A
对于有向图：
L^{out}=D^{out}-A\ ,\ L^{in}=D^{in}-A
我们规定记号 $\text{Sub}(M,i)$ 表示将矩阵 $M$ 去掉第 $i$ 行与第 $i$ 列的 $n-1$ 阶主子矩阵。
（自己乱搞的记号，我不知道有什么数学语言可以表示这个）
**矩阵树定理（Matrix-Tree Theorem）**
对于无向图：
$$t(G)=\det\ \text{Sub}(L(G),i)$$
其中 $t(G)$ 是图 $G$ 的生成树个数，$L(G)$ 是 $G$ 的 Laplace 矩阵，$i$ 是任意数。
对于有向图：
$$t^{out}(G)=\det\ \text{Sub}(L^{in}(G),rt)\ ,\ t^{in}(G)=\det\ \text{Sub}(L^{out}(G),rt)$$
其中 $t^{out}(G)$ 是外向（叶向）生成树个数，$t^{in}(G)$ 是内向（根向）生成树个数，$rt$ 是生成树的根。
**思路引导**
本题虽然是带权图，但是可以将边的权值视为重边数量。
根据乘法原理，点之间连接方式相同的生成树个数就是生成树上所有边的重边数量的乘积，正好与题目中“生成树的权值”对应。
那么题目就转化为了求图的所有生成树个数。使用矩阵树定理解决。
**代码**
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=1000000007;
int A[501][501],D[501][501],L[501][501];
int det(int a[501][501],int n){//行列式求值
int res=1,cur=1;
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n;++j){
while(a[i][i]){
int div=a[j][i]/a[i][i];
for(int k=i;k<=n;++k)
a[j][k]=(a[j][k]+MOD-div*a[i][k]%MOD)%MOD;
swap(a[i],a[j]),cur=-cur;
}
swap(a[i],a[j]),cur=-cur;
}
for(int i=1;i<=n;++i)res=res*a[i][i]%MOD;
res=(MOD+res*cur)%MOD;
return res;
}
int n,m,Typ;
signed main(){
cin>>n>>m>>Typ;
for(int i=1;i<=m;++i){
int u,v,w;
scanf("%lld%lld%lld",&u,&v,&w);
u--,v--;//删去第一行第一列，直接让第一行变成0，到时候不算就可以
D[v][v]=(D[v][v]+w)%MOD,A[u][v]=(A[u][v]+w)%MOD;
if(!Typ) D[u][u]=(D[u][u]+w)%MOD,A[v][u]=(A[v][u]+w)%MOD;
}
for(int i=1;i<n;++i)
for(int j=1;j<n;++j)L[i][j]=(D[i][j]+MOD-A[i][j])%MOD;
cout<<det(L,n-1);
}
```