行列式求值

struct Matrix {
    int n, m;
    vector< vector<int> > a;
    void clear() {
        vector<int> tmp(m + 1);
        a.resize(0);
        for (int i = 0; i <= n; i++) {
            a.push_back(tmp);
        }
    }
    Matrix(int _n, int _m) : n(_n), m(_m) {
        clear();
    }
    Matrix(int _n) : n(_n), m(_n) {
        clear();
    }
    Matrix() {}

    void rswap(int x, int y) {
        swap(a[x], a[y]);
    }
};

int det(Matrix A) {
    int n = A.n, ret = 1, cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!A.a[i][i]) {
            for(int j = i + 1; j <= n; j++) if (A.a[j][i]) {
                A.rswap(i, j); cnt++; break;
            }
        }
        if (!A.a[i][i]) return 0;
        for (int j = i + 1; j <= n; j++) {
            int t = 1LL * A.a[j][i] * ni(A.a[i][i]) % P;
            for (int k = i; k <= n; k++) {
                (A.a[j][k] += P - 1LL * t * A.a[i][k] % P) %= P;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        ret = 1LL * ret * A.a[i][i] % P;
    }
    return ret;
}

矩阵树定理

例题：P6178 【模板】Matrix-Tree 定理

题目大意：

给定一张 n 个结点 m 条边的带权图（可能为无向图，可能为有向图）。定义其一个生成树 T 的权值为 T 中所有边权的乘积。求其所有不同生成树的权值之和，对 10^9+7 取模。此题中有向图的生成树指的是以 1 为根的外向树。

输入：n,m,t，点数、边树，t=0 为无向图、t=1 为有向图。

解题思路：

• 生成树的个数

给出一个无向无权图,设 A 为邻接矩阵, D 为度数矩阵，则基尔霍夫矩阵即为 : K=D-A；
然后令 K’ 为 K 去掉第 k 行与第 k 列(k 任意)的结果(n-1 阶主子式)，\det(K’) 即为该图的生成树个数。

度数矩阵 D：若存在边 (x,y)，则 D[x][x]++; D[y][y]++;
邻接矩阵 A：若存在边 (x,y)，则 A[x][y]++; A[y][x]++;

• 加权扩展

度数矩阵 D：若存在边 (x,y,z)，则 D[x][x] += z; D[y][y] += z;
邻接矩阵 A：若存在边 (x,y,z)，则 A[x][y] += z; A[y][x] += z;

• 有向图的扩展

外向树：边从根向外。
度数矩阵 D：若存在边 (x,y,z)，则 D[y][y] += z;
邻接矩阵 A：若存在边 (x,y,z)，则 A[x][y] += z;

内向树：边从外到根。
度数矩阵 D：若存在边 (x,y,z)，则 D[x][x] += z;
邻接矩阵 A：若存在边 (x,y,z)，则 A[x][y] += z;

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int P = 1e9 + 7;

int ksm(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1, a = 1LL * a * a % P) {
        if (b & 1) {
            ret = 1LL * ret * a % P;
        }
    }
    return ret;
}
int ni(int a) {
    return ksm(a, P - 2);
}

struct Matrix {
    int n, m;
    vector< vector<int> > a;
    void clear() {
        vector<int> tmp(m + 1);
        a.resize(0);
        for (int i = 0; i <= n; i++) {
            a.push_back(tmp);
        }
    }
    Matrix(int _n, int _m) : n(_n), m(_m) {
        clear();
    }
    Matrix(int _n) : n(_n), m(_n) {
        clear();
    }
    Matrix() {}

    void rswap(int x, int y) {
        swap(a[x], a[y]);
    }
};

int det(Matrix A) {
    int n = A.n, ret = 1, cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (!A.a[i][i]) {
            for(int j = i + 1; j <= n; j++) if (A.a[j][i]) {
                A.rswap(i, j); cnt++; break;
            }
        }
        if (!A.a[i][i]) continue;
        for (int j = i + 1; j <= n; j++) {
            int t = 1LL * A.a[j][i] * ni(A.a[i][i]) % P;
            for (int k = i; k <= n; k++) {
                (A.a[j][k] += P - 1LL * t * A.a[i][k] % P) %= P;
            }
        }
    }
    for (int i = 1; i <= n; i++) {
        ret = 1LL * ret * A.a[i][i] % P;
    }
    return ret;
}

int Matrix_Tree(Matrix A, int rt = 0) {
    int n = A.n;
    if (!rt) rt = n;
    for (int i = rt; i < n; i++) {
        for (int j = 1; j <= n; j++) {
            A.a[i][j] = A.a[i + 1][j];
        }
    }
    for (int j = rt; j < n; j++) {
        for (int i = 1; i <= n; i++) {
            A.a[i][j] = A.a[i][j + 1];
        }
    }
    A.a.pop_back(); A.n = A.m = n - 1;
    for (int i = 0; i < n; i++) A.a[i].pop_back();
    return det(A);
}

int main(int argc, const char * argv[]) {
    int n, m, t; scanf("%d%d%d", &n, &m, &t);
    Matrix M(n);
    for (int i = 1, u, v, w; i <= m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        if (t == 0) {
            (M.a[u][u] += w) %= P; (M.a[v][v] += w) %= P;
            (M.a[u][v] += P - w) %= P; (M.a[v][u] += P - w) %= P;
        }
        else {
            (M.a[v][v] += w) %= P;
            (M.a[u][v] += P - w) %= P;
        }
    }
    printf("%d\n", Matrix_Tree(M, t));
    return 0;
}

应用举例：hdu6836