1016: [JSOI2008]最小生成树计数

/** @Author: LyuC* @Date: ??2017-09-07 21:48:20* @Last Modified by: ??LyuC* @Last Modified time: 2017-09-12 17:52:51*//* 题意：现在给出了一个简单无向加权图。你不满足于求出这个图的最小生成树，而希望知道 ???这个图中有多少个不同的最小生成树。（如果两颗最小生成树中至少有一条边不同，则 ???这两个最小生成树就是不同的）。由于不同的最小生成树可能很多，所以你只需要输出方 ???案数对31011的模就可以了。 思路：每个最小生成树的相同权值的边数是相同的，并且连通性是相同的，只需要枚举每个 ???权值的相同连通性，并且是最小生成树中这个权值的个数的方案数，然后组合一下就行了*/#include <bits/stdc++.h>#define MAXN 105#define MAXM 1005#define mod 31011using namespace std;struct Edge{ ???int u,v,w; ???bool operator < (const Edge & other) const{ ???????return w<other.w; ???}}edge[MAXM];vector<Edge>v[MAXM];int n,m;int x,y,z;int bin[MAXN];int root[MAXN];int vis[MAXM];//每种权值用到的数量int sum;int la;int pos;int res;inline int findx(int x){ ???int s=x; ???while(x!=bin[x]) ???????x=bin[x]; ???bin[s]=x; ???return x;}inline int Count(int x){ ???int s=0; ???while(x){ ???????if(x%2) ???????????s++; ???????x/=2; ???} ???return s;}inline void init(){ ???for(int i=0;i<=n;i++){ ???????bin[i]=i; ???????root[i]=i; ???} ???memset(vis,0,sizeof vis); ???for(int i=0;i<MAXM;i++) ???????v[i].clear(); ???res=1; ???pos=0; ???sum=0;}int main(){ ???// freopen("in.txt","r",stdin); ???scanf("%d%d",&n,&m); ???init(); ???for(int i=0;i<m;i++){ ???????scanf("%d%d%d",&x,&y,&z); ???????edge[i].u=x; ???????edge[i].v=y; ???????edge[i].w=z; ???} ???sort(edge,edge+m); ???//处理每种权值需要的边数 ???la=-1; ???for(int i=0;i<m;i++){ ???????if(edge[i].w!=la){ ???????????la=edge[i].w; ???????????bool flag=false; ???????????for(int j=i;edge[j].w==la;j++){ ???????????????int fx=findx(edge[j].u); ???????????????int fy=findx(edge[j].v); ???????????????if(fx!=fy){ ???????????????????flag=true; ???????????????????bin[fx]=fy; ???????????????????vis[pos]++; ???????????????????sum++; ???????????????} ???????????????v[pos].push_back(edge[j]); ???????????} ???????????pos++; ???????} ???} ???if(sum!=n-1){ ???????puts("0"); ???????return 0; ???} ???for(int i=0;i<pos;i++){//枚举每个阶段用到权值的边 ???????if(vis[i]==0) continue; ???????int tol=(1<<v[i].size()); ???????int cur=0;//可以的方案 ???????for(int j=0;j<tol;j++){ ???????????if(Count(j)!=vis[i]) continue; ???????????bool flag=true; ???????????memcpy(bin,root,sizeof root); ???????????for(int k=0;k<v[i].size();k++){ ???????????????if((j&(1<<k))!=0){//如果这条边存在 ???????????????????int fx=findx(v[i][k].u); ???????????????????int fy=findx(v[i][k].v); ???????????????????if(fx==fy){ ???????????????????????flag=false; ???????????????????????break; ???????????????????}else{ ???????????????????????bin[fx]=fy; ???????????????????} ???????????????} ???????????} ???????????if(flag==true) ???????????????cur++; ???????} ???????res=res*cur%mod; ???????memcpy(bin,root,sizeof root); ???????for(int j=0;j<v[i].size();j++){ ???????????int fx=findx(v[i][j].u); ???????????int fy=findx(v[i][j].v); ???????????if(fx!=fy){ ???????????????bin[fx]=fy; ???????????} ???????} ???????memcpy(root,bin,sizeof bin); ???} ???printf("%d\n",res%mod); ???return 0;}