题目概述

给出一张无向图，求生成树个数。

解题报告

大佬传送门：*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$ 列后得到的新矩阵。

行列式性质们：

1. $Det(A)=Det(A^{T})$

   • 定义式展开都是对应的，Candy?表示这说明了行列平等。

2. 两行或两列互换，行列式变号

   • 考虑一个序列两个元素交换后逆序对变化是奇数（我好像在之间就见过这个性质，但我不记得了QAQ），所以行列式就变号了。由此得知矩阵如果两行或两列相同，那么行列式为 $0$ 。

3. 单行单列乘上一个数 $k$ ，行列式 $\times k$

   • 考虑定义式，可以把 $k$ 提取出来。由此得知矩阵如果两行成比例，行列式也为 $0$ 。

4. 如果 $A,B$ 只有一行或一列不同，那么 $Det(A)+Det(B)$ 等于那一行或一列加起来后的矩阵的行列式

   • 考虑定义式，新矩阵的行列式显然可以拆成 $Det(A)+Det(B)$ 。

5. 很重要的性质：把矩阵的一行（列）乘上 $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;
}