[JSOI2008]最小生成树计数

 1 #include<iostream> 2 #include<cstdlib> 3 #include<cstdio> 4 #include<cmath> 5 #include<algorithm> 6 #include<cstring> 7 #include<queue> 8 #include<vector> 9 #define MAXN 50001010 #define RG register11 #define LL long long int12 using namespace std;13 const int INF=1e9;14 const int mod=31011;15 struct node{16 ??int x,y,w;17 }e[MAXN];18 int n,m;19 int fa[MAXN];20 int L[MAXN],R[MAXN],T[MAXN],cnt;21 int tot;22 int ans=1,sum;23 bool cmp(node a,node b){ return a.w<b.w;}24 int find(int x)25 {26 ??if(fa[x]==x) return x;27 ??else return find(fa[x]);28 }29 void dfs(int id,int now,int num)30 {31 ??if(now==R[id]+1)32 ????{33 ??????if(num==T[id]) sum++;34 ??????return;35 ????}36 ??int f1=find(e[now].x),f2=find(e[now].y);37 ??if(f1!=f2){38 ????fa[f2]=f1;39 ????dfs(id,now+1,num+1);40 ????fa[f1]=f1;fa[f2]=f2;41 ??}42 ??dfs(id,now+1,num);43 }44 int main()45 {46 ??freopen("1.in","r",stdin);47 ??scanf("%d%d",&n,&m);48 ??for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].w);49 ??sort(e+1,e+m+1,cmp);for(int i=1;i<=n;i++) fa[i]=i;50 ??for(int i=1;i<=m;i++)51 ????{52 ??????if(e[i].w!=e[i-1].w) R[cnt]=i-1,L[++cnt]=i;53 ??????int f1=find(e[i].x),f2=find(e[i].y);54 ??????if(f1!=f2){ fa[f2]=f1;T[cnt]++;tot++;}55 ????}56 ??R[cnt]=m;57 ??if(tot!=n-1){ printf("0\n");return 0;}58 ??for(int i=1;i<=n;i++) fa[i]=i;59 ??for(int i=1;i<=cnt;i++){60 ????sum=0;61 ????dfs(i,L[i],0);62 ????(ans*=sum)%=mod;63 ????for(int j=L[i];j<=R[i];j++){64 ??????int f1=find(e[j].x),f2=find(e[j].y);65 ??????if(f1!=f2){ fa[f2]=f1;}66 ????}67 ??}68 ??printf("%d\n",ans);69 ??return 0;70 }