Matrix-Tree (矩阵树) 定理

# Matrix-Tree (矩阵树) 定理
**：一个算生成树个数的东西**

## 思想
 1. 设 $D$ 为度数矩阵 $A$ 为邻接矩阵
 2. 令 $K = D - A$ , $K^{'}$为 $K$ 去掉 $i$ 行 $i$ 列后得到的矩阵
 3. $|K^{'}|$ 即为所求
 
 证明~~不会~~略
 
## 实现方式
###   有向图
 
 设当前加入边为$<x,y>$
  
 - 外向树
 则$D$为入度
 
 则$D[x][x]++,A[x][y]++$
 
 所以$K[x][x]--,K[x][y]--$
  - 内向树
 则$D$为出度
 
 则$D[y][y]++,A[x][y]++$
 
 所以$K[y][y]--,K[x][y]--$
 
 ### 无向图
 建正反两条边就ok了
 
 ### 带权の图
 把权值 $w$ 看作 $w$ 条重边
 
 做法和上面一样
 
 $|K^{'}|$也就是所有生成树边权乘积的总和
 
 （此处度数矩阵变成了相邻边的权值和）
 
## 代码
 [【模板】Matrix-Tree 定理](https://www.luogu.com.cn/problem/P6178)
 ```cpp
#include<bits/stdc++.h>
#define MAXN 305
#define mod 1000000007
#define int long long
using namespace std;
int a[MAXN][MAXN];
void print(int n){
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;j++)
			printf("%lld ",a[i][j]);
		printf("\n");
	}
}
int ans=1;
int solve(int n){
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			a[i][j]=(a[i][j]%mod+mod)%mod;
	for(int j=1;j<=n;++j){
		int k=-1;
		for(int i=j;i<=n;++i)
			if(a[i][j]){
				k=i;
				break;
		}
		if(k==-1)return 0;
		if(k!=j){swap(a[j],a[k]);ans=-ans;}
		for(int i=j+1;i<=n;++i)
			while(a[i][j]){
				int t=a[i][j]/a[j][j];
				for(int l=1;l<=n;++l)
					a[i][l]-=t*a[j][l],a[i][l]%=mod;
				if(a[i][j]==0)break;
				swap(a[i],a[j]);ans=-ans;
			}
		ans=ans*a[j][j]%mod;
	}
	return (ans%mod+mod)%mod;
}
signed main()
{
	int n,m,t;
	cin>>n>>m>>t;
	n--;
	int x,y,z;
	while(m--){
		scanf("%lld%lld%lld",&x,&y,&z);
		x--;y--;
		a[y][y]+=z;
		a[x][y]-=z;
		if(!t){
			a[x][x]+=z;
			a[y][x]-=z;
		}
	}
	printf("%lld",solve(n));
}
```

正在渲染内容...