Matrix-Tree定理 学习笔记
提出问题
给定一张n个点m条边的无向连通图，求它的生成树个数。
简单想法
那还不简单？深搜！反正我只要从任意一个点出发，不重不漏地把每个点搜一遍，就可以得到一颗生成树。然后我把生成树的数量加起来不就行了？
额，等等……
这玩意儿怎么写深搜，我好像不会耶……
搜一条链很简单，但搜出一棵树……哎呀妈呀怎么写啊！
就算搜出来了，怎么判重啊……
这令我想起了化学老师手动暴搜同分异构的情境，并且信誓旦旦地告诉我们，同分异构只能一个一个罗列。嗯，OIer当然要表示不服
好吧扯远了，我们回到正题
算了不写了，有兴趣的同学自己写写看吧
矩阵树定理
度数矩阵D
我们定义度数矩阵D的大小为n*n
度数矩阵里面的元素是这样的：
对于D[i][j]，其中i≠j，有D[i][j]=0
对于D[i][j]，其中i=j，有D[i][j]=图上i号点的度数（也就是与之相连的边的数量）
邻接矩阵A
我们定义领接矩阵A的大小为n*n
邻接矩阵里面的元素是这样的：
若i与j有一条边相连，则A[i][j]=A[j][i]=1
对于A[i][j]，其中i=j，有A[i][j]=0
Kichhoff矩阵C
我们定义C=D-A，减法定义为两矩阵中位置相同的元素相减
最终答案
删去拉C的任意一行以及任意一列，得到矩阵Ans
Ans的行列式的绝对值就是答案
问题转移
现在问题变成了怎样快速求一个行列式的值
翻看数学奥赛的一些矩阵相关书籍，发现上面介绍的行列式求值法都是所谓的“代数余子式”
这种方法是把n阶行列式拆成n个n-1阶行列式，然后再对每个拆出来的行列式进行同样的操作，直到拆成1阶，不难发现这种方法的时间复杂度是阶乘级别的，也就是O(n!)
我们不妨从一个简单的问题着手，思考如何优化行列式求值算法
试着写出一个“上三角行列式”，也就是左上-右下对角线的左下方元素均为0的行列式，用“代数余子式”法进行求值
发现了什么？答案等于左上-右下对角线上的元素之积！
其实很容易验证这个发现，只要每次都用最下面那行的元素来进行“代数余子式”中的降阶操作，就会发现一切
问题再转移
现在问题变成了怎样把一个普通行列式转化为“上三角行列式”
这其实就是高斯消元求线性方程组解的第一步——消去
那么问题就简单了，执行高斯消元第一步，然后将对角线元素相乘，就是答案
高斯消元法嘛，emm，有空再说
double G[105][105];
const double eps=1e-9;
int dcmp(double x)
{
if(fabs(x)<=eps) return 0;
else if(x>0) return 1;
else return -1;
}
double Gauss(int n)
{
n--;
for(int i=1;i<=n;i++)
{
int pos=i;
for(int j=i+1;j<=n;j++)
if(dcmp(G[j][i]-G[pos][i])>0) pos=j;
if(dcmp(G[pos][i])==0) return 0;
if(pos!=i)
for(int j=1;j<=n+1;j++) swap(G[i][j],G[pos][j]);
for(int j=i+1;j<=n;j++)
{
if(dcmp(G[j][i])==0) continue;
double t=G[j][i]/G[i][i];
for(int k=1;k<=n+1;k++)
G[j][k]-=t*G[i][k];
}
}
double ans=1;
for(int i=1;i<=n;i++) ans*=G[i][i];
return fabs(ans);
}
int main()
{
int T;
for(cin>>T;T;T--)
{
int n,m,a,b;
cin>>n>>m;
memset(G,0,sizeof(G));
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
G[a][a]++;
G[b][b]++;
G[a][b]--;
G[b][a]--;
}
printf("%.0lf\n",Gauss(n));
}
return 0;
}