不知为何使用路径压缩的并查集会WA。
#include<algorithm> #include<iostream> #include<cstdio> #define inf 0x7fffffff using namespace std; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } struct edge{ int x,y,v; }e[1001]; struct data{ int l,r,v; }a[1001]; int n,m,cnt,tot,ans=1,sum,fa[101]; inline int find(int x){ return fa[x]==x?x:find(fa[x]); } inline bool cmp(edge a,edge b){ return a.v<b.v; } void dfs(int x,int now,int k){ if(now==a[x].r+1){ if(k==a[x].v)sum++; return; } int p=find(e[now].x),q=find(e[now].y); if(p!=q){ fa[p]=q; dfs(x,now+1,k+1); fa[p]=p;fa[q]=q; } dfs(x,now+1,k); } int main(){ n=read();m=read(); for(int i=1;i<=m;i++) e[i]=(edge){read(),read(),read()}; for(int i=1;i<=n;i++)fa[i]=i; sort(e+1,e+m+1,cmp); for(int i=1;i<=m;i++){ if(e[i].v!=e[i-1].v){a[++cnt].l=i;a[cnt-1].r=i-1;} int p=find(e[i].x),q=find(e[i].y); if(p!=q){fa[p]=q;a[cnt].v++;tot++;} } a[cnt].r=m; if(tot!=n-1){printf("0");return 0;} for(int i=1;i<=n;i++)fa[i]=i; for(int i=1;i<=cnt;i++){ sum=0; dfs(i,a[i].l,0); ans=(ans*sum)%31011; for(int j=a[i].l;j<=a[i].r;j++){ int p=find(e[j].x),q=find(e[j].y); if(p!=q)fa[p]=q; } } printf("%d",ans); }