SPOJ HIGH Highways ——Matrix-Tree定理 高斯消元

【題目分析】

? ? Matrix-Tree定理+高斯消元

? ? 求矩陣行列式的值，就可以得到生成樹的個數。

? ? 至于證明，可以去看Vflea King（炸樹狂魔）的博客

【代碼】

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;#define eps 1e-8
#define maxn 15
double C[maxn][maxn],G[maxn][maxn],A[maxn][maxn];
int tt,n,m,a,b;void Gauss()
{double ret=1;for (int i=1;i<n;++i){for (int j=i+1;j<n;++j)while (fabs(C[j][i])>eps){double t=C[i][i]/C[j][i];for (int k=i;k<n;++k)C[i][k]-=t*C[j][k];for (int k=i;k<n;++k)swap(C[i][k],C[j][k]);ret*=-1;}ret=ret*C[i][i];}printf("%.0f\n",ret);
}int main()
{scanf("%d",&tt);while (tt--){memset(G,0,sizeof G);memset(A,0,sizeof A);memset(C,0,sizeof C);scanf("%d%d",&n,&m);for (int i=1;i<=m;++i){int a,b;scanf("%d%d",&a,&b);G[a][a]+=1;G[b][b]+=1;A[a][b]=A[b][a]=1;}for (int i=1;i<=n;++i)for (int j=1;j<=n;++j)C[i][j]=G[i][j]-A[i][j];Gauss();}
}