【模板】Matrix-Tree 定理

前置知识：

我们用到的矩阵，也就是基尔霍夫矩阵的任意一个代数余子式是所有生成树的边权积的和。

当所有边边权为1时求的就是生成树的个数了。

若边权不为$1$,求的就是

定义其一个生成树 TT 的权值为 TT 中所有边权的乘积。

所有不同生成树的权值之和

做法

我们以下设$(x,y,z)$为$xx$到$yy$有一条边权为$zz$的无向/有向 边。

1.无向图

假设现在给定一个图 $G$ .

度数矩阵D:若存在边$(x,y,z)$,则 $D[x][x]+=z;D[y][y]+=z;$

邻接矩阵C:若存在边$(x,y,z)$,则$C[x][y]+=z;C[y][x]+=z;$

图G的基尔霍夫矩阵 $AA=DD-CC$ 。

删去任意一行和任意一列，求剩下的矩阵行列式即可。

2.有向图

假设现在给定一个图G.

度数矩阵D:若存在边$(x,y,z)$,则 外向树中$D[y][y]+=z;$

内向树中$D[x][x]+=z;$

邻接矩阵C:若存在边$(x,y,z)$,则 内向树和外向树中均为$C[x][y]+=z;$

图G的基尔霍夫矩阵$AA=DD-CC$。

删去指定的根所在的行和列，求剩下的矩阵行列式即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 309;
const int mod = 1e9+7;
int n,m,type,a[309][309],ans=1;
int quick(int x,int n,int mod)
{
	int ans = 1;
	for( ; n ; n>>=1,x = x*x%mod )
		if( n&1 )	ans = ans*x%mod;
	return ans; 
}
void guass(int n)
{
	for(int i=2;i<=n;i++)
	{
		for(int j=i+1;j<=n;j++)
			if( !a[i][i]&&a[j][i] )
			{
				ans = -ans;	swap( a[i],a[j] );//交换行列式两行,值相反 
				break;
			}
		int inv = quick( a[i][i],mod-2,mod );
		for(int j=i+1;j<=n;j++)
		{
			int temp = a[j][i]*inv%mod;
			for(int k=i;k<=n;k++)
				a[j][k] = ( a[j][k]-a[i][k]*temp%mod )%mod;
		}
	}
}
signed main()
{
	cin >> n >> m >> type;//t为0是无向图,1是有向图
	for(int i=1;i<=m;i++)
	{
		int x,y,z; scanf("%lld%lld%lld",&x,&y,&z);
		if( !type )
		{
			a[x][x] = ( a[x][x]+z )%mod, a[y][y] = ( a[y][y]+z )%mod;
			a[x][y] = ( a[x][y]-z )%mod, a[y][x] = ( a[y][x]-z )%mod;	
		}	
		else
			a[y][y] = ( a[y][y]+z )%mod, a[x][y] = ( a[x][y]-z )%mod;
	}
	guass(n);
	for(int i=2;i<=n;i++)
		ans = ( ans*a[i][i] )%mod;
	cout << ( ans%mod+mod )%mod;
}