【模板】Matrix-Tree 定理
题目链接:luogu P6178
题目大意
给你一个无向图或有向图,然后让你求它有多少种以 1 为根的外向生成树。
思路
玄学玩意儿。
原理自己上去搜题解,我也说不清,就讲讲大概流程把。
我们弄一个矩阵 \(K\)。(\(a_{i,j}\) 是邻接矩阵)(如果有重边就是边权相加)
\(K_{i,i}=\sum\limits_{j=1}^na_{j,i}\)(外向树)
\(K_{i,i}=\sum\limits_{j=1}^na_{i,j}\)(内向树)
\(K_{i,j}=-a_{i,j}(i\neq j)\)
然后这个矩阵你弄个一个 \(n-1\) 阶的主子式(如果是有根的就只能不要根的行列),然后用那个矩阵跑行列式就是答案了。
代码
#include<cstdio>
#include<algorithm>
#define ll long long
#define mo 1000000007
using namespace std;
int n, m, t, x, y;
ll z, a[301][301];
ll work(int l, int r) {//行列式
ll ans = 1, zf = 1, tmp;
for (int i = l; i <= r; i++) {
int k = i;
for (int j = i + 1; j <= r; j++)
if (a[j][i] > a[k][i]) k = j;
if (!a[k][i]) return 0;
if (k != i) swap(a[i], a[k]), zf = -zf;
for (int j = i + 1; j <= r; j++) {
if (a[j][i] > a[i][i]) swap(a[j], a[i]), zf = -zf;
while (a[j][i]) {
tmp = a[i][i] / a[j][i];
for (int k = i; k <= r; k++)
a[i][k] = (a[i][k] + a[j][k] * (mo - tmp) % mo) % mo;
swap(a[i], a[j]); zf = -zf;
}
}
ans = ans * a[i][i] % mo;
}
if (zf == -1) return (mo - ans) % mo;
return ans;
}
int main() {
scanf("%d %d %d", &n, &m, &t);
for (int i = 1; i <= m; i++) {
scanf("%d %d %lld", &x, &y, &z);
a[x][y] = (a[x][y] - z + mo) % mo;
a[y][y] = (a[y][y] + z) % mo;
if (!t) a[y][x] = (a[y][x] - z + mo) % mo, a[x][x] = (a[x][x] + z) % mo;//无向边
}
printf("%lld", work(2, n));//删去根所在的行列
return 0;
}