矩阵树定理

· · 个人记录

矩阵树定理

先定义基尔霍夫(Kirchhoff)矩阵：

令deg_i为i节点的入度(所有指向i点的边的权值和)。

令A_{i,j}=\begin{cases} deg_i, (i=j)\\ 0, (i\neq j) \end{cases},

B为邻接矩阵。

则基尔霍夫矩阵=A-B。

无向图

如果边权均为1，且有重边无自环，那么基尔霍夫矩阵任意一个n-1阶主子式(去掉序号相同的一行一列)的行列式的绝对值为其生成树的个数。

证明不会。

考虑到生成树的个数就是各种形态的生成树的个数之和，而一种形态的生成树的个数就是各条边重边数量之积(乘法原理)。所以生成树的个数就是每种形态的生成树各边的重边数量之积的和。

考虑将重边数量看作这条边的边权，那么就能得到每种形态的生成树的边权之积的和就是生成树总数。

有向图

先定义外向树是各边均由父亲指向儿子的有向树，内向树是各边均由儿子指向父亲的有向树。

其实用不着定义，两者处理方法一样

类比无向图，无向树没有定根所以可以随意取n-1阶主子式。那么有向图直接去掉根所对应的一行一列就行。

其他与无向图差不多。

Matrix-Tree 定理

直接套模板就行。

以前一直用的约旦消元法，这次终于打了高斯消元法，感觉更方便。

对于高斯消元的一般情况(即不求逆元)，可以考虑用类似辗转相除的方法用第i行消掉第j行。

Code

#include<iostream>
#include<cstdio>
#define ll long long
#define R register
using namespace std;
const int mod=1e9+7;
const int maxn=3e2;
int n,m,t;
ll a[maxn+5][maxn+5];
inline ll read(){
    ll a=0,b=1;
    char s=getchar();
    while(s<48||s>57){
        if(s=='-') b=-1;
        s=getchar();
    }
    while(s>=48&&s<=57)
        a=(a<<1)+(a<<3)+s-48,s=getchar();
    return a*b;
}
inline void print(){
    for(R int i=1;i<=n;i=-~i){
        for(R int j=1;j<=n;j=-~j)
            printf("%lld ",a[i][j]);
        putchar('\n');
    }
    putchar('\n');
}
inline void swap(ll &a,ll &b){a^=b^=a^=b;}
inline ll calc(){
    int s=1;
    for(R int i=2;i<n;i=-~i){
        for(R int j=i+1;j<=n;j=-~j){
            while(a[j][i]){
                int num=a[i][i]/a[j][i];
                for(R int k=i;k<=n;k=-~k){
                    a[i][k]=(a[i][k]-a[j][k]*1LL*num%mod)%mod;
                    swap(a[i][k],a[j][k]);
                }
                s*=-1;
            }
        }
    }
    ll ans=1LL*s;
    for(R int i=2;i<=n;i=-~i){
        ans=ans*a[i][i]%mod;
        ans=(ans+mod)%mod;
    }
    return ans;
}
int sta[20],top;
inline void write(ll x){
    if(!x) putchar('0');
    else{
        if(x<0) putchar('-'),x=~x+1;
        while(x) sta[++top]=x%10,x/=10;
        while(top) putchar(sta[top--]+48);
    }
    putchar('\n');
}
int main(){
    n=read(),m=read(),t=read();
    for(R int i=1;i<=m;i=-~i){
        int u=read(),v=read();
        ll w=read();
        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[u][v]=(a[u][v]-w)%mod;
            a[v][v]=(a[v][v]+w)%mod;
        }
    }
    write(calc());
    return 0;
}