这个问题就是经典的生成树记数问题,题目为spoj p104 highway。

  首先我们引入Matrix-Tree定理,由kirchhoff证明,定理的概述为,对于图G,我们定义若干个矩阵,

    D[G],Dij=(i!=j)?0:vi;这里vi为节点i的度数。

    A[G],Aij=存在边(u,v),即A为图G的连通01矩阵。

    定义Kirchhoff Matrix C[G]=D[G]-A[G],那么C[G]的任意一个n-1阶主子式的行列式的绝对值为图G生成树个数。

这样这个问题就可以比较容易的解决了,行列式的求法为将矩阵用类似于消元的方法消成上三角矩阵(其实我也是记住的代码= =)。

//By BLADEVIL
#include <cstdio>
#include <cstring>
#define maxn 20 using namespace std; int a[maxn][maxn];
double g[maxn][maxn]; bool zero(double x)
{
return (((x<)?-x:x)<1e-);
} void swap(double &a,double &b)
{double c=a;a=b;b=c;} double delte(double a[maxn][maxn],int n)
{
int sign=;
double ans=;
for (int i=;i<=n;i++)
{
if (zero(a[i][i]))
{
int j;
for (j=i+;(j<=n)&&(zero(a[j][i]));j++);
if (j>n) return ;
for (int k=i+;k<=n;k++) swap(a[i][k],a[j][k]);
sign++;
}
ans*=a[i][i];
for (int j=i+;j<=n;j++) a[i][j]/=a[i][i];
for (int j=i+;j<=n;j++)
for (int k=i+;k<=n;k++)
a[j][k]-=a[i][j]*a[k][i];
}
if (sign&) ans=-ans;
return ans;
} void solve()
{
int n,m;
scanf("%d%d",&n,&m);
memset(g,,sizeof g); memset(a,,sizeof a);
for (int i=;i<=m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
a[x][y]=a[y][x]=;
g[x][x]++; g[y][y]++;
}
n--;
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
if (a[i][j]) g[i][j]=-;
printf("%.0f\n",delte(g,n));
} int main()
{
int task;
scanf("%d",&task);
while (task--) solve();
return ;
}
05-24 15:12