简述
Kirchhoff 矩阵树定理（简称矩阵树定理）解决了一张图的生成树个数计数问题。
主要步骤
无向图
假设现在给定一个无向图\(G\)
定义度数矩阵\(D\)：若存在边\((u,v,w)\)，则\(D[u][u]+=w,D[v][v]+=z\)
定义邻接矩阵\(C\)：若存在边\((u,v,w)\)，则\(C[u][v]+=w,C[v][u]+=w\)
图G的基尔霍夫矩阵\(A=D-C\)
删去任意一行和任意一列，求剩下的矩阵行列式，即为所有生成树的边权积的和
当所有边边权为1时就是生成树的个数
有向图
假设现在给定一个有向图\(G\)
定义度数矩阵\(D\)：若存在边\((u,v,w)\)，则外向树中\(D[v][v]+=z\)，内向树中\(D[u][u]+=w\)
定义邻接矩阵\(C\)：若存在边\((u,v,w)\)，则内向树和外向树中均\(C[u][v]+=w\)
图G的基尔霍夫矩阵\(A=D-C\)
删去任意一行和任意一列，求剩下的矩阵行列式，即为所有生成树的边权积的和
当所有边边权为1时就是生成树的个数
code
给定一张 \(n\) 个结点 \(m\) 条边的带权图（可能为无向图，可能为有向图）。
定义其一个生成树 \(T\) 的权值为 \(T\) 中所有边权的乘积。
求其所有不同生成树的权值之和，对 \(10^9\) 取模。
题目链接
题解
点击查看代码
#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
#define int long long//
using namespace std;
namespace Q{
il int rd(){
ri int x=0;bool f=0;ri char c=getchar();
while(!isdigit(c)) f|=(c=='-'),c=getchar();
while(isdigit(c)) x=x*10+(c^48),c=getchar();
return f?-x:x;
}
il void wt(int x){
if(x<0) x=-x,putchar('-');
if(x>=10) wt(x/10);
return putchar(x%10+48),void();
}
il int qpow(int a,int b,int p=1e9+7){
ri int as=1;
while(b>0){
if(b&1) as=as*a%p;
a=a*a%p,b>>=1;
}
return as;
}
il int inv(int a,int p=1e9+7){
return qpow(a,p-2,p);
}
} using namespace Q;
cs int N=305,mod=1e9+7;
int n,m,t;
struct matrix{
int o[N][N];
il int getdet(int p=1e9+7){
ri int as=1,iv,l;
for(ri int i=2;i<=n;++i){
if(!o[i][i]){
for(ri int j=i+1;j<=n;++j){
as*=-1,swap(o[i],o[j]);
}
}
iv=inv(o[i][i]);
for(ri int j=i+1;j<=n;++j){
l=o[j][i]*iv%p;
for(ri int k=i;k<=n;++k){
o[j][k]=(o[j][k]-o[i][k]*l%p+p)%p;
}
}
as=as*o[i][i]%p;
if(!as) return 0;
}
return as;
}
}a;
signed main(){
n=rd(),m=rd(),t=rd();
for(ri int i=1,u,v,w;i<=m;++i){
u=rd(),v=rd(),w=rd()%mod;
a.o[v][v]=(a.o[v][v]+w)%mod,a.o[u][v]=(a.o[u][v]-w+mod)%mod;
if(!t) a.o[u][u]=(a.o[u][u]+w)%mod,a.o[v][u]=(a.o[v][u]-w+mod)%mod;
}
wt(a.getdet());
return 0;
}