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

#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int mod=31011;struct node{ ???int x,y,d;}a[1100];struct line{ ???int l,r,v;}s[1100];int cnt;int cmp(const void *xx,const void *yy){ ???node n1=*(node *)xx; ???node n2=*(node *)yy; ???if(n1.d>n2.d)return 1; ???else if(n1.d<n2.d)return -1; ???else return 0;}int fa[1100];int findfa(int x){ ???if(x!=fa[x])return findfa(fa[x]); ???return x;}int sum;void dfs(int x,int i,int k){ ???if(i==s[x].r+1) ???{ ???????if(k==s[x].v)sum++; ???????return ; ???} ???int fx=findfa(a[i].x),fy=findfa(a[i].y); ???if(fx!=fy) ???{ ???????fa[fx]=fy; ???????dfs(x,i+1,k+1); ???????fa[fx]=fx;fa[fy]=fy; ???} ???dfs(x,i+1,k);}int main(){ ???int n,m; ???scanf("%d%d",&n,&m); ???for(int i=1;i<=m;i++)scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].d); ???qsort(a+1,m,sizeof(node),cmp); ???for(int i=1;i<=n;i++)fa[i]=i; ???????int tot=0; ???for(int i=1;i<=m;i++) ???{ ???????if(a[i].d!=a[i-1].d) ???????{ ???????????s[cnt].r=i-1; ???????????cnt++; ???????????s[cnt].l=i;s[cnt].v=0; ???????} ???????????????int fx=findfa(a[i].x),fy=findfa(a[i].y); ???????if(fx!=fy) ???????{ ???????????fa[fx]=fy; ???????????tot++;s[cnt].v++; ???????} ???} ???s[cnt].r=m; ???if(tot<n-1){printf("0\n");return 0;} ???????for(int i=1;i<=n;i++)fa[i]=i; ???int ans=1; ???for(int i=1;i<=cnt;i++) ???{ ???????sum=0; ???????dfs(i,s[i].l,0); ???????ans=(ans*sum)%mod; ???????for(int j=s[i].l;j<=s[i].r;j++) ???????{ ???????????int fx=findfa(a[j].x),fy=findfa(a[j].y); ???????????if(fx!=fy)fa[fx]=fy; ???????} ???} ???printf("%d\n",ans); ???return 0;}