bzoj 1016 [JSOI2008]最小生成树计数——matrix tree（相同权值的边为阶段缩点）（码力）

#include<iostream>#include<cstdio>#include<cstring>#include<vector>#include<cmath>#include<algorithm>using namespace std;const int N=105,M=1005,mod=31011;int n,m,fa[N],pa[N],c[N][N],a[N][N],ans=1;//ans=1bool vis[N];vector<int> v[N];struct Ed{ ?int x,y,w; ?bool operator< (const Ed &b)const ?{return w<b.w;}}ed[M];int find(int a,int f[]){return f[a]==a?a:find(f[a],f);} //加上路径压缩会变慢！！！ int gauss(int n){ ?bool fx=0;int ret=1; ?for(int i=1;i<=n;i++) ???for(int j=1;j<=n;j++)a[i][j]%=mod;// ?for(int i=1;i<=n;i++) ???{ ?????int k=i; ?????for(int j=i+1;j<=n;j++)if(abs(a[j][i])>abs(a[k][i]))k=j; ?????if(k!=i) ???{ ?????fx=!fx;for(int j=i;j<=n;j++)swap(a[i][j],a[k][j]); ???} ?????for(int j=i+1;j<=n;j++) ???while(a[j][i]) ?????{ ???????fx=!fx;int tmp=a[i][i]/a[j][i]; ???????for(int l=i;l<=n;l++) ?????????{ ???????int tp=a[i][l];a[i][l]=a[j][l];//i=j ???????a[j][l]=(tp-tmp*a[j][l])%mod;//j=i%j ?????????} ?????} ?????(ret*=a[i][i])%=mod; ???} ???return (ret*(fx?-1:1)+mod)%mod;}int main(){ ?scanf("%d%d",&n,&m); ?for(int i=1;i<=n;i++)fa[i]=i,pa[i]=i; ?for(int i=1;i<=m;i++) ?????scanf("%d%d%d",&ed[i].x,&ed[i].y,&ed[i].w); ?sort(ed+1,ed+m+1); ?for(int i=1;i<=m;i++) ???{ ?????int f1=find(ed[i].x,fa),f2=find(ed[i].y,fa); ?????if(f1!=f2){ ?????????vis[f1]=1;vis[f2]=1; ?????????pa[find(f1,pa)]=find(f2,pa);c[f1][f2]++;c[f2][f1]++; ?????}// ?????if(f1==f2)continue;//!!!!!!! ?????if(ed[i+1].w!=ed[i].w||i==m) ???{ ?????for(int j=1;j<=n;j++) ???????{ ?????????if(!vis[j])continue; ?????????v[find(j,pa)].push_back(j); ?????????vis[j]=0; ???????} ?????for(int j=1;j<=n;j++) ???????{ ?????????if(v[j].size()<=1)continue; ?????????memset(a,0,sizeof a);//! ?????????int siz=v[j].size(); ?????????for(int l0=0;l0<siz;l0++) ???????for(int l1=l0+1;l1<siz;l1++) ?????????{ ???????????int x=v[j][l0],y=v[j][l1],t=c[x][y];//x=v[j][l0],don‘t use l0 directly ???????????a[l0+1][l0+1]+=t;a[l1+1][l1+1]+=t; ???????????a[l0+1][l1+1]-=t;a[l1+1][l0+1]-=t;//but here is l0/1, for in gauss the bh must from 1 and be continous ?????????} ?????????(ans*=gauss(siz-1))%=mod; ?????????for(int k=0;k<siz;k++)fa[v[j][k]]=j;//fa -> pa ???????} ?????for(int j=1;j<=n;j++) ???????{ ?????????fa[j]=pa[j]=find(j,fa);v[j].clear(); ???????} ???} ???} ?for(int i=1;i<n;i++)if(find(i,fa)!=find(i+1,fa)){printf("0");return 0;} ?printf("%d",ans); ?return 0;}

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int N=105,M=1005,mod=31011;int n,m,p0,p1,col[N],cnt,head[N],xnt,fnw,ans=1,fa[N],bh[N],tot;bool used[M<<1],vis[N],nd[N],tvis[N];struct Ed{ ???int next,x,y,w; ???Ed(int x=0,int y=0,int w=0):x(x),y(y),w(w) {} ???bool operator< (const Ed &b)const ???????{return w<b.w;}}ed[M<<1];struct Matrix{ ???int a[N][N]; ???void init(){memset(a,0,sizeof a);} ???Matrix operator- (const Matrix &b)const ???{ ???????Matrix c;c.init(); ???????for(int i=1;i<tot;i++) ???????????for(int j=1;j<tot;j++) ???????????????c.a[i][j]=(a[i][j]-b.a[i][j])%mod;// ???????return c; ???}}d,l,r;int find(int a){return fa[a]==a?a:fa[a]=find(fa[a]);}void add(int x,int y,int w){ ???ed[++xnt]=Ed(x,y,w); ???ed[++xnt]=Ed(y,x,w); ???if(find(x)!=find(y))fa[find(x)]=find(y);}void dfst(int cr){ ???tvis[cr]=1;bh[cr]=++tot; ???for(int i=head[cr],v;i;i=ed[i].next) ???????if(used[i]&&!tvis[ed[i].y])dfst(ed[i].y);}void dfsx(int cr,int f) ???//dfs处理好这一块的度数矩阵和邻接矩阵 { ???vis[cr]=1; ???for(int i=head[cr],v;i;i=ed[i].next) ???????if(used[i]&&(v=ed[i].y)!=f) ???????{ ???????????d.a[bh[cr]][bh[cr]]++;if(!vis[v])d.a[bh[v]][bh[v]]++; ???????????l.a[bh[cr]][bh[v]]=l.a[bh[v]][bh[cr]]=1; ???????????if(!vis[v])dfsx(v,cr); ???????}}void gauss(){ ???int fx=1,ret=1; ???for(int i=1;i<tot;i++)//<tot，少一行一列 ????{ ???????int nw=i; ???????for(int j=i+1;j<tot;j++)if(abs(r.a[j][i])>abs(r.a[nw][i]))nw=j; ???????if(nw!=i) ???????{ ???????????fx=-fx;for(int l=i;l<tot;l++)swap(r.a[i][l],r.a[nw][l]); ???????} ???????for(int j=i+1;j<tot;j++) ???????????while(r.a[j][i]) ???????????{ ???????????????int tmp=r.a[i][i]/r.a[j][i]; ???????????????for(int l=i;l<tot;l++) ???????????????{ ???????????????????int tp=r.a[i][l];r.a[i][l]=r.a[j][l];//i=j; ???????????????????r.a[j][l]=(tp-r.a[j][l]*tmp)%mod;//j=i%j ???????????????} ???????????????fx=-fx; ???????????} ???????(ret*=r.a[i][i])%=mod; ???//不要在上面赋值：消下面的时候可能换过来！ ????} ???ret=(ret*fx+mod)%mod; ???(fnw*=ret)%=mod;}void cal(int x) ???//当前权值的一个个联通块 { ???d.init();l.init(); ???memcpy(tvis,vis,sizeof vis);tot=0;//bh! ???dfst(x);dfsx(x,0); ???r=d-l; ???gauss();}void dfs(int cr){ ???col[cr]=cnt; ???for(int i=head[cr];i;i=ed[i].next) ???????if(used[i]&&!col[ed[i].y]) ???????????dfs(ed[i].y);}void solve() ???//一层 { ???memset(nd,0,sizeof nd);memset(used,0,sizeof used); ???for(int i=p0;i<=p1;i++) ???????if(ed[i].x!=ed[i].y) ???//边的两边连的是已经缩点后的 ????????????used[i]=1,nd[ed[i].x]=1,nd[ed[i].y]=1; ???//能用的边和涉及的点 ????memset(vis,0,sizeof vis);memset(bh,0,sizeof bh);fnw=1; ???for(int i=1;i<=cnt;i++)if(!vis[i]&&nd[i])cal(i); ???//每个联通块 ????(ans*=fnw)%=mod; ???cnt=0;memset(col,0,sizeof col); ???????//cnt:现在有多少点(缩点后) ???for(int i=1;i<=cnt;i++)if(!col[i])cnt++,dfs(i); ???????//缩点 ????for(int i=p1+1;i<=xnt;i++)ed[i].x=col[ed[i].x],ed[i].y=col[ed[i].y];}int main(){ ???scanf("%d%d",&n,&m);int x,y,w; ???for(int i=1;i<=n;i++)fa[i]=i; ???for(int i=1;i<=m;i++)scanf("%d%d%d",&x,&y,&w),add(x,y,w); ???for(int i=2;i<=n;i++)if(find(i-1)!=find(i)){printf("0");return 0;}// ???sort(ed+1,ed+xnt+1);cnt=n; ???for(int i=1;i<=xnt;i++) ???{ ???????ed[i].next=head[ed[i].x]; ???????head[ed[i].x]=i; ???} ???for(int i=1;i<=xnt;i++) ???{ ???????p0=i;while(ed[i+1].w==ed[i].w)i++;p1=i; ???????solve(); ???} ???printf("%d",ans); ???return 0;}