bzoj 1016 [JSOI2008]最小生成樹計數——matrix tree（相同權值的邊為階段縮點）（碼力）...

題目：https://www.lydsy.com/JudgeOnline/problem.php?id=1016

就是縮點，每次相同權值的邊構成的聯通塊求一下matrix tree。注意gauss里的編號應該是從1到...的連續的。

學習了一個TJ。用了vector。自己曾寫過一個只能過樣例的。都放上來吧。

路徑壓縮的話會慢？循環里ed[i].w!=ed[i+1].w的話會慢？

#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=1
bool 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=ja[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+1;i++)//
    {if(ed[i-1].w!=ed[i].w||i==m+1)//
    {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 directlya[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();}}int f1=find(ed[i].x,fa),f2=find(ed[i].y,fa);if(f1==f2)continue;vis[f1]=1;vis[f2]=1;pa[find(f1,pa)]=find(f2,pa);c[f1][f2]++;c[f2][f1]++;}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<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=1
bool 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=ja[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 directlya[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;
}

?