https://blog.csdn.net/zhaoruixiang1111/article/details/79185927
为了学一个矩阵树定理 从行列式开始学(就当提前学线代了。。
矩阵数定理:
截图来自于上述论文
裸题。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std; const int N=;
const double eps=1e-;
double G[N][N]; double myabs(double x){return x> ? x:-x;} double guass(int n)
{
double ans=;
for(int i=;i<=n;i++)
{
int r=i;
for(int j=i+;j<=n;j++)
if(myabs(G[j][i])>myabs(G[r][i])) r=j;
if(r!=i)
{
for(int j=;j<=n;j++) swap(G[i][j],G[r][j]);
ans*=-;
}
if(G[i][i]==) return ;//一开始忘了判断,WA了好几发
for(int j=i+;j<=n;j++)//row
{
for(int k=n;k>=i;k--)//col
G[j][k]-=G[j][i]/G[i][i]*G[i][k];
}
} for(int i=;i<=n;i++) ans*=G[i][i];
return myabs(ans);
} int main()
{
//freopen("a.in","r",stdin);
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
memset(G,,sizeof(G));
for(int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
G[x][x]++;G[y][y]++;
G[x][y]=-;G[y][x]=-;//不是--,而是直接等于-1
}
printf("%.0lf\n",guass(n-));
}
return ;
}