网站创建教程,你做的网站可视区域多少钱,做淘宝客最大的网站是叫什么名字,四川省建设建设监理协会网站题目#xff1a;https://www.lydsy.com/JudgeOnline/problem.php?id1016 就是缩点#xff0c;每次相同权值的边构成的联通块求一下matrix tree。注意gauss里的编号应该是从1到...的连续的。 学习了一个TJ。用了vector。自己曾写过一个只能过样例的。都放上来吧。 路径压缩的…题目https://www.lydsy.com/JudgeOnline/problem.php?id1016 就是缩点每次相同权值的边构成的联通块求一下matrix tree。注意gauss里的编号应该是从1到...的连续的。 学习了一个TJ。用了vector。自己曾写过一个只能过样例的。都放上来吧。 路径压缩的话会慢循环里ed[i].w!ed[i1].w的话会慢 #includeiostream
#includecstdio
#includecstring
#includevector
#includecmath
#includealgorithm
using namespace std;
const int N105,M1005,mod31011;
int n,m,fa[N],pa[N],c[N][N],a[N][N],ans1;//ans1
bool vis[N];
vectorint v[N];
struct Ed{int x,y,w;bool operator (const Ed b)const{return wb.w;}
}ed[M];
int find(int a,int f[]){return f[a]a?a:find(f[a],f);} //加上路径压缩会变慢
int gauss(int n)
{bool fx0;int ret1;for(int i1;in;i)for(int j1;jn;j)a[i][j]%mod;//for(int i1;in;i){int ki;for(int ji1;jn;j)if(abs(a[j][i])abs(a[k][i]))kj;if(k!i){fx!fx;for(int ji;jn;j)swap(a[i][j],a[k][j]);}for(int ji1;jn;j)while(a[j][i]){fx!fx;int tmpa[i][i]/a[j][i];for(int li;ln;l){int tpa[i][l];a[i][l]a[j][l];//ija[j][l](tp-tmp*a[j][l])%mod;//ji%j}}(ret*a[i][i])%mod;}return (ret*(fx?-1:1)mod)%mod;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i)fa[i]i,pa[i]i;for(int i1;im;i)scanf(%d%d%d,ed[i].x,ed[i].y,ed[i].w);sort(ed1,edm1);for(int i1;im1;i)//{if(ed[i-1].w!ed[i].w||im1)//{for(int j1;jn;j){if(!vis[j])continue;v[find(j,pa)].push_back(j);vis[j]0;}for(int j1;jn;j){if(v[j].size()1)continue;memset(a,0,sizeof a);//!int sizv[j].size();for(int l00;l0siz;l0)for(int l1l01;l1siz;l1){int xv[j][l0],yv[j][l1],tc[x][y];//xv[j][l0],dont use l0 directlya[l01][l01]t;a[l11][l11]t;a[l01][l11]-t;a[l11][l01]-t;//but here is l0/1, for in gauss the bh must from 1 and be continous}(ans*gauss(siz-1))%mod;for(int k0;ksiz;k)fa[v[j][k]]j;//fa - pa}for(int j1;jn;j){fa[j]pa[j]find(j,fa);v[j].clear();}}int f1find(ed[i].x,fa),f2find(ed[i].y,fa);if(f1f2)continue;vis[f1]1;vis[f2]1;pa[find(f1,pa)]find(f2,pa);c[f1][f2];c[f2][f1];}for(int i1;in;i)if(find(i,fa)!find(i1,fa)){printf(0);return 0;}printf(%d,ans);return 0;
} #includeiostream
#includecstdio
#includecstring
#includevector
#includecmath
#includealgorithm
using namespace std;
const int N105,M1005,mod31011;
int n,m,fa[N],pa[N],c[N][N],a[N][N],ans1;//ans1
bool vis[N];
vectorint v[N];
struct Ed{int x,y,w;bool operator (const Ed b)const{return wb.w;}
}ed[M];
int find(int a,int f[]){return f[a]a?a:find(f[a],f);} //加上路径压缩会变慢
int gauss(int n)
{bool fx0;int ret1;for(int i1;in;i)for(int j1;jn;j)a[i][j]%mod;//for(int i1;in;i){int ki;for(int ji1;jn;j)if(abs(a[j][i])abs(a[k][i]))kj;if(k!i){fx!fx;for(int ji;jn;j)swap(a[i][j],a[k][j]);}for(int ji1;jn;j)while(a[j][i]){fx!fx;int tmpa[i][i]/a[j][i];for(int li;ln;l){int tpa[i][l];a[i][l]a[j][l];//ija[j][l](tp-tmp*a[j][l])%mod;//ji%j}}(ret*a[i][i])%mod;}return (ret*(fx?-1:1)mod)%mod;
}
int main()
{scanf(%d%d,n,m);for(int i1;in;i)fa[i]i,pa[i]i;for(int i1;im;i)scanf(%d%d%d,ed[i].x,ed[i].y,ed[i].w);sort(ed1,edm1);for(int i1;im;i){int f1find(ed[i].x,fa),f2find(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(f1f2)continue;//!!!!!!!if(ed[i1].w!ed[i].w||im){for(int j1;jn;j){if(!vis[j])continue;v[find(j,pa)].push_back(j);vis[j]0;}for(int j1;jn;j){if(v[j].size()1)continue;memset(a,0,sizeof a);//!int sizv[j].size();for(int l00;l0siz;l0)for(int l1l01;l1siz;l1){int xv[j][l0],yv[j][l1],tc[x][y];//xv[j][l0],dont use l0 directlya[l01][l01]t;a[l11][l11]t;a[l01][l11]-t;a[l11][l01]-t;//but here is l0/1, for in gauss the bh must from 1 and be continous}(ans*gauss(siz-1))%mod;for(int k0;ksiz;k)fa[v[j][k]]j;//fa - pa}for(int j1;jn;j){fa[j]pa[j]find(j,fa);v[j].clear();}}}for(int i1;in;i)if(find(i,fa)!find(i1,fa)){printf(0);return 0;}printf(%d,ans);return 0;
} 改一下循环(慢) #includeiostream
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N105,M1005,mod31011;
int n,m,p0,p1,col[N],cnt,head[N],xnt,fnw,ans1,fa[N],bh[N],tot;
bool used[M1],vis[N],nd[N],tvis[N];
struct Ed{int next,x,y,w;Ed(int x0,int y0,int w0):x(x),y(y),w(w) {}bool operator (const Ed b)const{return wb.w;}
}ed[M1];
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 i1;itot;i)for(int j1;jtot;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 ihead[cr],v;i;ied[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 ihead[cr],v;i;ied[i].next)if(used[i](ved[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 fx1,ret1;for(int i1;itot;i)//tot少一行一列 {int nwi;for(int ji1;jtot;j)if(abs(r.a[j][i])abs(r.a[nw][i]))nwj;if(nw!i){fx-fx;for(int li;ltot;l)swap(r.a[i][l],r.a[nw][l]);}for(int ji1;jtot;j)while(r.a[j][i]){int tmpr.a[i][i]/r.a[j][i];for(int li;ltot;l){int tpr.a[i][l];r.a[i][l]r.a[j][l];//ij;r.a[j][l](tp-r.a[j][l]*tmp)%mod;//ji%j}fx-fx;}(ret*r.a[i][i])%mod; //不要在上面赋值消下面的时候可能换过来 }ret(ret*fxmod)%mod;(fnw*ret)%mod;
}
void cal(int x) //当前权值的一个个联通块
{d.init();l.init();memcpy(tvis,vis,sizeof vis);tot0;//bh!dfst(x);dfsx(x,0);rd-l;gauss();
}
void dfs(int cr)
{col[cr]cnt;for(int ihead[cr];i;ied[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 ip0;ip1;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);fnw1;for(int i1;icnt;i)if(!vis[i]nd[i])cal(i); //每个联通块 (ans*fnw)%mod;cnt0;memset(col,0,sizeof col); //cnt:现在有多少点(缩点后)for(int i1;icnt;i)if(!col[i])cnt,dfs(i); //缩点 for(int ip11;ixnt;i)ed[i].xcol[ed[i].x],ed[i].ycol[ed[i].y];
}
int main()
{scanf(%d%d,n,m);int x,y,w;for(int i1;in;i)fa[i]i;for(int i1;im;i)scanf(%d%d%d,x,y,w),add(x,y,w);for(int i2;in;i)if(find(i-1)!find(i)){printf(0);return 0;}//sort(ed1,edxnt1);cntn;for(int i1;ixnt;i){ed[i].nexthead[ed[i].x];head[ed[i].x]i;}for(int i1;ixnt;i){p0i;while(ed[i1].wed[i].w)i;p1i;solve();}printf(%d,ans);return 0;
} 只能过样例的 转载于:https://www.cnblogs.com/Narh/p/9274486.html
