记录编号	144694	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008] 最小生成树计数	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2014-12-25 15:59:16	内存使用	0.35 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#define Mod 31011
#define Maxn 1010
#define Maxm 1010
using namespace std;
struct node{
	int x,y,v;
}a[Maxm];
vector<int> G[Maxm];
int father[Maxn],a0[Maxn]={0},N,tot[Maxn]={0};
int total,n,m,ans=1;
bool cmp(const node &a,const node &b){
	return a.v<b.v;
}
int hash(int x){
	return lower_bound(a0+1,a0+N+1,x)-a0;
}
int find(int x){
	return father[x]==x? x:find(father[x]);
}
void dfs(int co,int t,int now){
	if(t==G[co].size()){
		if(now==tot[co]) total=(total+1)%Mod;
	}
	else{
		int p=G[co][t],r1,r2;
		r1=find(a[p].x); r2=find(a[p].y);
		if(r1!=r2){
			father[r2]=r1;
			dfs(co,t+1,now+1);
			father[r2]=r2; father[r1]=r1;
		}
		dfs(co,t+1,now);
	}
}
bool kruskar(){
	sort(a+1,a+m+1,cmp);
	for(int i=1;i<=n;i++) father[i]=i;
	for(int i=1;i<=m;i++){
		int r1=find(a[i].x),r2=find(a[i].y);
		if(r1!=r2){
			father[r2]=r1;
			tot[hash(a[i].v)]++;
		}
	}
	for(int i=2;i<=n;i++)
		if(find(i)!=find(i-1)) return false;
	return true;
}
void work(){
    for(int i=1;i<=m;i++) G[hash(a[i].v)].push_back(i);
	for(int i=1;i<=n;i++) father[i]=i;
	for(int co=1;co<=N;co++){
		total=0; dfs(co,0,0);
		ans=(ans*total)%Mod;
 		for(int i=0;i<G[co].size();i++){
			int p=G[co][i];
			int r1=find(a[p].x),r2=find(a[p].y);
			if(r1!=r2) father[r2]=r1;
		}
	}
	printf("%d",ans);
}
void init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v);
		a0[++a0[0]]=a[i].v;
	}
	sort(a0+1,a0+a0[0]+1); N=1;
	for(int i=2;i<=a0[0];i++){
		if(a0[i]!=a0[i-1]) a0[++N]=a0[i];
	}
}
int main(){
	freopen("bzoj_1016.in","r",stdin);
	freopen("bzoj_1016.out","w",stdout);
	init();
	if(kruskar()) work();
	else printf("0");
	return 0;
}