题目链接：BZOJ - 1016
题目分析
最小生成树的两个性质：
同一个图的最小生成树，满足：
1）同一种权值的边的个数相等
2）用Kruscal按照从小到大，处理完某一种权值的所有边后，图的连通性相等
这样，先做一次Kruscal求出每种权值的边的条数，再按照权值从小到大，对每种边进行 DFS， 求出这种权值的边有几种选法。
最后根据乘法原理将各种边的选法数乘起来就可以了。
特别注意：在DFS中为了在向下DFS之后消除决策影响，恢复f[]数组之前的状态，在DFS中调用的Find()函数不能路径压缩。
代码
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm> using namespace std; const int MaxN = 100 + 5, MaxM = 1000 + 5, Mod = 31011; int n, m, Top, Sum, Cnt;
int f[MaxN], L[MaxM], R[MaxM], Num[MaxM]; typedef long long LL;
LL Ans; struct Edge
{
int u, v, w;
} E[MaxM]; inline bool Cmp(Edge e1, Edge e2)
{
return e1.w < e2.w;
} inline int Find(int x, int o)
{
int i, j, k;
j = x;
while (j != f[j]) j = f[j];
if (o == 1) return j;
i = x;
while (i != j)
{
k = i;
i = f[i];
f[k] = j;
}
return j;
} void DFS(int Type, int x, int y)
{
if (x == R[Type] + 1)
{
if (y == Num[Type]) ++Cnt;
return;
}
int fx, fy;
fx = Find(E[x].u, 1); fy = Find(E[x].v, 1);
if (fx != fy)
{
f[fx] = fy;
DFS(Type, x + 1, y + 1);
f[fx] = fx;
}
DFS(Type, x + 1, y);
} int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i)
scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].w);
sort(E + 1, E + m + 1, Cmp);
Top = 0; Sum = 0;
int fx, fy;
for (int i = 1; i <= n; ++i) f[i] = i;
for (int i = 1; i <= m; ++i)
{
if (i == 1 || E[i].w != E[i - 1].w) L[++Top] = i;
R[Top] = i;
fx = Find(E[i].u, 0); fy = Find(E[i].v, 0);
if (fx != fy)
{
f[fx] = fy;
++Num[Top];
++Sum;
}
}
if (Sum != n - 1)
{
printf("0\n");
return 0;
}
for (int i = 1; i <= n; ++i) f[i] = i;
Ans = 1;
for (int i = 1; i <= Top; ++i)
{
if (Num[i] == 0) continue;
Cnt = 0;
DFS(i, L[i], 0);
Ans = Ans * (LL)Cnt % Mod;
for (int j = L[i]; j <= R[i]; ++j)
{
fx = Find(E[j].u, 0); fy = Find(E[j].v, 0);
if (fx != fy) f[fx] = fy;
}
}
printf("%d\n", (int)Ans);
return 0;
}