【分析】
不知道结论是不可以做的吧？表示也不会矩阵树定理。。dfs方法也要知道一些证明才能说明其准确性。
【以后的博客都要留坑了？
安利两种题解：
1、我的打法：（不看都不知道为什么这样做是对的）
https://blog.sengxian.com/solutions/bzoj-1016
http://www.cnblogs.com/lcf-2000/p/5575412.html
2、矩阵树（没打这种，还不会）
http://blog.csdn.net/jarily/article/details/8902509
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 1100
#define Maxm 10100
#define Mod 31011 struct node
{
int x,y,c;
}t[Maxm]; bool cmp(node x,node y) {return x.c<y.c;}
int a[Maxm],l[Maxm],r[Maxm],fa[Maxn]; int ffa(int x)
{
return x==fa[x]?x:ffa(fa[x]);
} int ct;
void ffind(int x,int nw,int h)
{
if(nw==r[x]+)
{
if(h==a[x]) ct++;
return;
}
int x1=ffa(t[nw].x),x2=ffa(t[nw].y);
if(x1!=x2)
{
fa[x1]=x2;
ffind(x,nw+,h+);
fa[x1]=x1;
}
ffind(x,nw+,h);
} int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=m;i++)
{
scanf("%d%d%d",&t[i].x,&t[i].y,&t[i].c);
}
sort(t+,t++m,cmp);
int cnt=,tot=;
for(int i=;i<=n;i++) fa[i]=i;
for(int i=;i<=m;i++)
{
if(i==||t[i].c!=t[i-].c)
{
r[cnt]=i-;l[++cnt]=i;
a[cnt]=;
}
int x1=ffa(t[i].x),x2=ffa(t[i].y);
if(x1!=x2)
{
fa[x1]=x2;
a[cnt]++;
tot++;
} }r[cnt]=m;
if(tot!=n-) printf("0\n");
else
{
for(int i=;i<=n;i++) fa[i]=i;
int ans=;
for(int i=;i<=cnt;i++)
{
ct=;
ffind(i,l[i],);
ct%=Mod;
ans=ans*ct;ans%=Mod;
for(int j=l[i];j<=r[i];j++)
{
int x1=ffa(t[j].x),x2=ffa(t[j].y);
if(x1!=x2) fa[x1]=x2;
}
}
printf("%d\n",ans);
}
return ;
}
2017-02-28 13:58:04