P4208 [JSOI2008]最小生成树计数

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cctype>using namespace std;template <typename T> inline void read(T &x){ ???char c=getchar(); x=0; ???while(!isdigit(c)) c=getchar(); ???while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();}const int mod=31011;struct edge{int from,to,dis;}a[1002],c[1002];inline bool cmp(const edge &A,const edge &B) {return A.dis<B.dis;}int n,m,ans=1,k,fa1[102],fa2[102],f[102][102],b[102]; bool vis[102];inline int find1(int x){return fa1[x]==x ? x:fa1[x]=find1(fa1[x]);}inline int find2(int x){return fa2[x]==x ? x:fa2[x]=find2(fa2[x]);}inline int det(int t){ ???int res=1; ???for(int i=1;i<t;++i){ ???????for(int j=i+1;j<t;++j){ ???????????while(f[j][i]){ //辗转相除 ???????????????int div=f[i][i]/f[j][i]; ???????????????for(int k=i;k<t;++k) f[i][k]=(f[i][k]-1LL*f[j][k]*div%mod+mod)%mod; ???????????????swap(f[i],f[j]); res=-res; ???????????} ???????} ???????res=(res+mod)%mod*f[i][i]%mod; ???}return (res+mod)%mod;}inline void mt(int st,int ed){ ???memset(vis,0,sizeof(vis)); ???memset(f,0,sizeof(f)); ???for(int i=st;i<=ed;++i){ ???????c[i]=((edge){find1(a[i].from),find1(a[i].to),a[i].dis}); //新边，编号为原连通块的编号 ???????if(c[i].from==c[i].to) continue; ???????if(!vis[c[i].from]) vis[c[i].from]=1; ???????if(!vis[c[i].to]) vis[c[i].to]=1; ???}int cnt=0; ???for(int i=1;i<=n;++i) if(vis[i]) b[++cnt]=i,fa2[cnt]=cnt; //新点 ???for(int i=st;i<=ed;++i){ ???????if(c[i].from==c[i].to) continue; ???????int r1=find1(c[i].from),r2=find1(c[i].to); ???????if(r1!=r2) fa1[r1]=r2,++k; ???????int u=lower_bound(b+1,b+cnt+1,c[i].from)-b; ???????int v=lower_bound(b+1,b+cnt+1,c[i].to)-b; ???????++f[u][u];++f[v][v]; ???????f[u][v]=(f[u][v]-1+mod)%mod; //每次减法取模 ???????f[v][u]=(f[v][u]-1+mod)%mod; ???????r1=find2(u),r2=find2(v); ???????if(r1!=r2) fa2[r1]=r2; ???} ???for(int i=1;i<cnt;++i){ //为了防止新图不连通，在每个连通块间加入一条唯一任意边。这并不会影响生成树方案数 ???????int r1=find2(i),r2=find2(i+1); ???????if(r1==r2) continue; ???????fa2[r1]=r2; ++f[r1][r1];++f[r2][r2]; ???????f[r1][r2]=(f[r1][r2]-1+mod)%mod; ???????f[r2][r1]=(f[r2][r1]-1+mod)%mod; ???}ans=1LL*ans*det(cnt)%mod;}int main(){ ???read(n); read(m); ???for(int i=1;i<=n;++i) fa1[i]=i; ???for(int i=1;i<=m;++i) read(a[i].from),read(a[i].to),read(a[i].dis); ???sort(a+1,a+m+1,cmp); ???for(int i=1,j;i<=m&&k<n-1;i=j){ ???????for(j=i+1;j<=m;++j) if(a[i].dis!=a[j].dis) break; ???????if(j-i>1) {mt(i,j-1); continue;} //相同权值的边超过1条就要计算生成树的方案了 ???????int r1=find1(a[i].from),r2=find1(a[i].to); ???????if(r1!=r2) fa1[r1]=r2,++k; ???}if(k<n-1) ans=0; ???printf("%d",ans); ???return 0;}