发布时间：2025-05-22

矩阵树定理

构造$Laplace$矩阵，求生成树计数

无向图情况：

$L_{ii}=deg(i),L_{i,j}=-e(i,j)$,$e(i,j)$为边数

有向图情况：

入度矩阵：$L_{ii}^{in}=deg^{in}(i)，L_{i,j}^{in}=-e(i,j)$

出度矩阵：$L_{ii}^{out}=deg^{out}(i)，L_{i,j}^{out}=-e(i,j)$

得到这个矩阵后，随便删掉一行一列后进行高斯消元得到上三角矩阵，对角线上值的积就是生成树的个数。

无向图：求$det(L)$

根向树形图，求$det(L^{out})$，删去第$k$行列，就是以$k$为根，下面同理

叶向树形图：求$det(L^{in})$

生成树总和边权计数

int a[310][310];
inline int det(int m){
	int res=1;
	bool flag_neg=false;
	for(int i=1;i<=m;++i){
		int k=i;
		while(k<=m&&!a[k][i])++k;
		if(k>m)return 0;
		if(k!=i){
			for(int j=i;j<=m;++j)swap(a[i][j],a[k][j]);
			flag_neg^=1;
		}
		res=1ll*res*(a[i][i]+mod)%mod;
		int t=qpow(a[i][i],mod-2);
		for(int k=i+1;k<=m;++k){
			int t0=1ll*t*a[k][i]%mod;
			for(int j=i;j<=m;++j)a[k][j]=(a[k][j]-1ll*a[i][j]*t0)%mod;
		}
	}
	return flag_neg?mod-res:res; 
}
void solve(){
	int n,m,t;
	cin>>n>>m>>t;
	n--;// 这里有向树以1为根，因此删除第1行第1列
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		u--,v--;
		if(!t){
			a[u][u]=(a[u][u]+w)%mod;
			a[v][v]=(a[v][v]+w)%mod;
			a[u][v]=(a[u][v]-w)%mod;
			a[v][u]=(a[v][u]-w)%mod;
		}
		else{
			// 叶向树(外向树)：a[v][v]+=w,a[v][u]-=w
			// 根向树(内向树)：a[u][u]+=w,a[v][u]-=w
			a[v][v]=(a[v][v]+w)%mod;
			a[v][u]=(a[v][u]-w)%mod;
		}
	}
	cout<<det(n)<<"\n";
}

无向图计数例子

有$n-1$个公司，每个公司可以修建若干条边，$n-1$条边只能由不同的公司修建

答案就是=用到$n$个公司的情况-用到$n-1$个公司的情况+$n-2$的情况....

for(int i=0;i<1<<m;i++){
    int cnt=__builtin_popcountll(i);
    int mask=((1<<m)-1)^i;
    memset(a,0,sizeof a);
    for(int j=0;j<m;j++){
        if(mask>>j&1){
            for(auto [u,v]:e[j]){
                a[u][u]++,a[v][v]++;
                a[u][v]--,a[v][u]--;
            }
        }
    }
    int tmp=det(n-1);
    if(cnt&1)ans=(ans+mod-tmp)%mod;
    else ans=(ans+tmp)%mod;
}
cout<<ans<<"\n";