【学习笔记】矩阵树定理

前言

矩阵树定理可以统计无向图的生成树个数或所有生成树权值之和，以及有向图的根向/叶向树形图个数或所有树形图权值之和

其中，一个生成树/树形图的权值定义为其所有边的边权之积

p.s. 以下内容均默认可以有重边（视为不同的边），但不能有自环

统计权值之和

对于一个有 n 个点的图 G，设其度数矩阵为 D, 邻接矩阵为 C，则其基尔霍夫矩阵 A=D-C

无向图

若存在一条边 (x,y,w)，则 D_{x,x},D_{y,y} 均加 w，C_{x,y},C_{y,x} 均加 w

则 A 的任意一个 n-1 阶主子式即为权值之和

有向图

若存在一条边 (x,y,w)，若统计根向（内向）树形图则 D_{x,x} 加 w，若统计叶向（外向）树形图则 D_{y,y} 加 w；对于根向/叶向树形图均为 C_{x,y} 加 w

则 A 删除根节点对应的行和列，剩下的 n-1 阶主子式即为权值之和

统计生成树/树形图个数

只需将边权全部视为1，权值之和即为生成树/树形图个数

Code

Luogu P6178 【模板】Matrix-Tree 定理

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 305
#define MOD 1000000007
#define inv(x) (fpow(x, MOD - 2))
#define int long long

using namespace std;

int n, m, typ;
int a[MAX_N][MAX_N];

int fpow(int x, int k) {
    int ans = 1;
    while (k) {
        if (k & 1) {
            ans = ans * x % MOD;
        }
        x = x * x % MOD, k >>= 1;
    }
    return ans;
}

void del(int r) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != r && j != r) {
                int x = i > r ? i - 1 : i;
                int y = j > r ? j - 1 : j;
                a[x][y] = a[i][j];
            }
        }
    }
}

int det(int a[][MAX_N], int n) {
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        if (!a[i][i]) {
            for (int j = i + 1; j <= n; j++) {
                if (a[j][i]) {
                    for (int k = 1; k <= n; k++) {
                        swap(a[i][k], a[j][k]);
                    }
                    ans = -ans;
                    break;
                }
            }
        }
        int t = inv(a[i][i]);
        for (int j = i + 1; j <= n; j++) {
            int f = a[j][i] * t % MOD;
            for (int k = i; k <= n; k++) {
                a[j][k] = (a[j][k] - a[i][k] * f % MOD) % MOD;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        ans = ans * a[i][i] % MOD;
    }
    return (ans % MOD + MOD) % MOD;
}

signed main() {
    scanf("%lld%lld%lld", &n, &m, &typ);
    int x, y, z;
    for (int i = 1; i <= m; i++) {
        scanf("%lld%lld%lld", &x, &y, &z);
        if (x != y) {
            if (typ == 0) {
                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;
            }
        }
    }
    del(1);
    printf("%lld", det(a, n - 1));
}