ZigZagK的博客 - SPOJ
type: channel
link: https://zigzagk.top/category/SPOJ
items: [矩阵树定理]SPOJ(HIGH)【Highways】题解

[矩阵树定理]SPOJ(HIGH)【Highways】题解
type: item
date: 2019-01-08T09:34:00+08:00
description: 题目概述给出一张无向图，求生成树个数。解题报告大佬传送门：*ZJ，Candy?。矩阵树定理裸题，先来讲（瞎扯）一波行列式：行列式定义式：$Det(A)=\sum_{P}(-1)^{\tau(P)}\sum_{i=1}^{n}A_{i,P_i}$ ，其中 $A$ 是 $n$ 行 $n$ 列矩阵，$P$ 是 $n$ 的排列，$\tau(P)$ 是 $P$ 的逆序对数。$n-1$ 阶主子式：删除 $i$ 行 $i$ 列后得到的新矩阵。行列式性质们：$Det(A)=Det(A^{T})$定义式展开都是对应的，Candy?表示这说明了行列平等。两行或两列互换，行列式变号考虑一个序列两个元素交换后逆序对变化是奇数（我好像在之间就见过这个性质，但我不记得了QAQ），所以行列式就变号了。由此得知矩阵如果两行或两列相同，那么行列式为 $0$ 。单行单列乘上一个数 $k$ ，行列式 $\times k$考虑定义式，可以把 $k$ 提取出来。由此得知矩阵如果两行成比例，行列式也为 $0$ 。如果 $A,B$ 只有一行或一列不同，那么 $Det(A)+Det(B)$ 等于那一行或一列加起来后的矩阵的行列式考虑定义式，新矩阵的行列式显然可以拆成 $Det(A)+Det(B)$ 。很重要的性质：把矩阵的一行（列）乘上 $k$ 加到另外一行（列）上，行列式不变根据性质 $3$ 和 $4$ ，新矩阵的行列式可以拆成两个，其中一个是原矩阵的行列式，另一个是加到的行（列）变成 $k$ 倍的被加的行（列）的矩阵的行列式，第二个矩阵两行（列）成比例，行列式为 $0$ 。根据上述性质（尤其是性质 $5$ ）我们可以用高斯消元来得出行列式。基尔霍夫矩阵：一张图的度数矩阵减去邻接矩阵。度数矩阵：$A_{i,i}$ 为 $i$ 点度数，其余为 $0$ 。邻接矩阵：$A_{i,j}$ 表示 $i,j​$ 之间边的个数。矩阵树定理：一张图的生成树个数是该图基尔霍夫矩阵的任意一个 $n-1$ 阶主子式的行列式。证明我试图去看了……但是，毕竟是试图QAQ……示例程序#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long double DB; const int maxn=12; int te,n,m;DB a[maxn+5][maxn+5],ans; inline int fcmp(DB a,DB b) {if (fabs(a-b)<1e-8) return 0;return a<b?-1:1;} inline double Det(int n,DB ans=1){ for (int i=1;i<=n;i++){ for (int j=i;j<=n;j++) if (fcmp(a[j][i],0)>0) {if (i!=j) swap(a[i],a[j]),ans=-ans;goto YES;} return 0;YES:for (int j=i+1;j<=n;j++) {DB t=a[j][i]/a[i][i];for (int k=i;k<=n;k++) a[j][k]-=t*a[i][k];} }for (int i=1;i<=n;i++) ans*=a[i][i];return ans; } int main(){ freopen("program.in","r",stdin);freopen("program.out","w",stdout); for (scanf("%d",&te);te;te--){ scanf("%d%d",&n,&m);memset(a,0,sizeof(a)); for (int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),a[x][x]++,a[y][y]++,a[x][y]--,a[y][x]--; printf("%.0f\n",fabs(Det(n-1))); }return 0; }