相关生成树计数的问题可以参考周冬的论文...
| SPOJ HIGH | Highways |
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define zero(x) (((x)>0?(x):(-x))<1e-15)
using namespace std;
const int MAXN = 110;
double a[MAXN][MAXN], b[MAXN][MAXN];
int G[MAXN][MAXN];
int N, M;
/*
*生成树计数
*1、G的度数矩阵D[G]是一个n*n的矩阵，并且满足：当i≠j时,dij=0；当i=j时，dij等于vi的度数。
*2、G的邻接矩阵A[G]也是一个n*n的矩阵， 并且满足：如果vi、vj之间有边直接相连，则aij=1，否则为0。
*我们定义G的Kirchhoff矩阵(也称为拉普拉斯算子)C[G]为C[G]=D[G]-A[G]，则Matrix-Tree定理可以描述为：
*G的所有不同的生成树的个数等于其Kirchhoff矩阵C[G]任何一个n-1阶主子式的行列式的绝对值。
*所谓n-1阶主子式，就是对于r(1≤r≤n)，将C[G]的第r行、第r列同时去掉后得到的新矩阵，用Cr[G]表示。
*/
double Det(double a[MAXN][MAXN], int n)
{
int i, j, k, sign = 0;
double ret = 1, t;
for(i = 0; i < n; ++i)
for(j = 0; j < n; ++j)
b[i][j] = a[i][j];
for(i = 0; i < n; ++i)
{
if(zero(b[i][i]))
{
for(j = i + 1; j < n; ++j)
{
if(!zero(b[j][i]))
break;
}
if(j == n)
return 0;
for(k = i; k < n; ++k)
t = b[i][k], b[i][k] = b[j][k], b[j][k] = t;
sign++;
}
ret *= b[i][i];
for(k = i + 1; k < n; ++k)
b[i][k] /= b[i][i];
for(j = i + 1; j < n; ++j)
for(k = i + 1; k < n; ++k)
b[j][k] -= b[j][i] * b[i][k];
}
if(sign & 1)
ret = - ret;
return ret;
}
int main()
{
int T, u, v;
scanf("%d", &T);
while (T--)
{
scanf("%d %d", &N, &M);
memset(G, 0, sizeof(G));
memset(a, 0, sizeof(a));
while(M--)
{
scanf("%d %d", &u, &v);
G[u-1][v-1] = G[v-1][u-1] = 1;
}
for(int i = 0; i < N; ++i)
{
int d = 0;
for (int j = 0; j < N; ++j) if(G[i][j]) d++;
a[i][i] = d;
}
for(int i = 0; i < N; ++i)
{
for (int j = 0; j < N; ++j)
{
if (G[i][j]) a[i][j] = -1;
}
}
double ans = Det(a, N - 1);
printf("%0.0lf\n", ans);
}
return 0;
}
HDU 4408最小生成树计数问题(直接参考别人的代码,当做模板用吧)
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define int64 long long
using namespace std;
const int MAX=105; //点的个数
const int MAXE=1005; //边的个数
struct node
{
int set[MAX];
void init(int n)
{
int i;
for(i=0;i<=n;i++) set[i]=i;
}
int find(int x)
{
if(set[x]!=x) set[x]=find(set[x]);
return set[x];
}
int Union(int x,int y)
{
int xx=find(x);
int yy=find(y);
if(xx==yy) return -1;
set[xx]=yy;
return 1;
}
};
struct Node
{
int u,v,dis;
};
node a,b,c;
int n,m;
Node e[MAXE];
int visit[MAX];
vector<int> g[MAX];
int64 p[MAX][MAX],MOD,deg[MAX][MAX];
int cmp(Node a,Node b)
{
return a.dis<b.dis;
}
int64 DET(int64 a[][MAX],int n)
{
int i,j,k;
int64 temp=1,t;
for(i=0;i<n;i++) for(j=0;j<n;j++) a[i][j]%=MOD;
for(i=1;i<n;i++)
{
for(j=i+1;j<n;j++) while(a[j][i])
{
t=a[i][i]/a[j][i];
for(k=i;k<n;k++)
{
a[i][k]-=a[j][k]*t;
a[i][k]%=MOD;
}
for(k=i;k<n;k++)
{
t=a[i][k];
a[i][k]=a[j][k];
a[j][k]=t;
}
temp=-temp;
}
temp=temp*a[i][i]%MOD;
}
return (temp+MOD)%MOD;
}
int64 cal_MST_count()
{
sort(e+1,e+m+1,cmp);
int i,j,k,t,x,y,pre=e[1].dis;
int64 ans=1;
a.init(n);
b.init(n);
memset(visit,0,sizeof(visit));
memset(deg,0,sizeof(deg));
for(i=0;i<=n;i++) g[i].clear();
for(t=1;t<=m+1;t++)
{
if(e[t].dis!=pre||t==m+1)
{
for(i=1;i<=n;i++) if(visit[i])
{
k=b.find(i);
g[k].push_back(i);
visit[i]=0;
}
for(i=1;i<=n;i++) if(g[i].size())
{
memset(p,0,sizeof(p));
for(j=0;j<g[i].size();j++) for(k=j+1;k<g[i].size();k++)
{
x=g[i][j];
y=g[i][k];
p[j][k]=p[k][j]=-deg[x][y];
p[j][j]+=deg[x][y];
p[k][k]+=deg[x][y];
}
ans=ans*DET(p,g[i].size())%MOD;
for(j=0;j<g[i].size();j++) a.set[g[i][j]]=i;
}
memset(deg,0,sizeof(deg));
for(i=1;i<=n;i++)
{
b.set[i]=a.find(i);
g[i].clear();
}
if(t==m+1) break;
pre=e[t].dis;
}
x=a.find(e[t].u);
y=a.find(e[t].v);
if(x==y) continue;
visit[x]=visit[y]=1;
b.Union(x,y);
deg[x][y]++;
deg[y][x]++;
}
if(!m) return 0;
for(i=2;i<=n;i++) if(b.find(i)!=b.find(1)) return 0;
return ans;
}
int main()
{
while(scanf("%d%d%lld",&n,&m,&MOD),n||m||MOD)
{
int i;
for(i=1;i<=m;i++)
{
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].dis);
}
int64 x=cal_MST_count();
printf("%lld\n",x);
}
return 0;
}