题目：
http://www.lydsy.com/JudgeOnline/problem.php?id=1016对于一个图的最小生成树，特定权值的边的长度是一定的，而且插入这些边所形成的连通块是一样的。
先做一遍最小生成树确定每种边权的边的数量然后dfs计数即可。
要注意的是可能存在图是不连通的情况。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <map>
using namespace std;
const int MaxM=1500;
const int MaxN=500;
struct line
{
int x,y,value;
};
int n,m,father[MaxN],ans=1,t[MaxN];
line a[MaxM];
bool vis[MaxN];
bool cmp(line a,line b)
{
return a.value<b.value;
}
int find(int x)
{
if (father[x]==x)
{
return x;
}
return find(father[x]);
}
int kruscal(int st,int &i)
{
int ans=0;
for (i=st;i<m && a[i].value==a[st].value;i++)
{
int x=find(a[i].x),y=find(a[i].y);
if (x!=y)
{
father[x]=y;
ans++;
}
}
return ans;
}
int dfs(int now,int ed,int value,int nowv)
{
if (now>=ed)
{
if (nowv==value)
{
return 1;
}
return 0;
}
if (ed-now<value-nowv)
{
return 0;
}
if (value==nowv)
{
return 1;
}
int ans=dfs(now+1,ed,value,nowv);
int x=find(a[now].x),y=find(a[now].y);
if (x!=y)
{
int t=father[x];
father[x]=y;
ans+=dfs(now+1,ed,value,nowv+1);
father[x]=t;
}
return ans;
}
void pd(int x)
{
vis[x]=1;
for (int i=0;i<m;i++)
{
if (a[i].x==x && vis[a[i].y]==0)
{
pd(a[i].y);
}
if (a[i].y==x && vis[a[i].x]==0)
{
pd(a[i].x);
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=0;i<m;i++)
{
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].value);
}
pd(1);
for (int i=1;i<=n;i++)
{
if (vis[i]==0)
{
printf("0\n");
return 0;
}
}
sort(a,a+m,cmp);
for (int i=1;i<=n;i++)
{
father[i]=i;
}
for (int i=0;i<m;)
{
memcpy(t,father,sizeof(t));
int now,ii,tot;
now=kruscal(i,ii);
memcpy(father,t,sizeof(t));
tot=dfs(i,ii,now,0);
ans=(ans*(tot%31011))%31011;
kruscal(i,ii);
i=ii;
}
printf("%d\n",ans);
return 0;
}