简述

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;
}

原文链接: https://www.cnblogs.com/windymoon/p/17071208.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/314429

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

矩阵树定理

简述

主要步骤

无向图

有向图

code

相关推荐