首页 > 代码库 > BZOJ 3569 DZY Loves Chinese II 高斯消元
BZOJ 3569 DZY Loves Chinese II 高斯消元
题目大意:给定一个【魞歄连通图】,多次询问当图中某k条边消失时这个图是否联通 强制在线
我们找到这个图的任意一棵生成树 然后对于每条非树边将其的权值赋为一个随机数
对于每条树边 我们将这条树边的权值设为所有覆盖这条树边的边权的异或和
那么图不连通当且仅当删除一条树边和覆盖这条树边的所有边集 而由于刚才的处理一条树边和覆盖这条边的所有边集的异或和为零
于是问题转化成了对于给定的k条边是否存在一个边权的异或和为零的子集 果断高斯消元 由于使用了随机化所以碰撞率极低
好方法学习了。。。构思真是巧妙
记得设随机数种子否则会被卡掉
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 100100 using namespace std; struct abcd{ int to,next; }table[1001001]; int head[M],tot=1; int n,m,q,last_ans; int a[500500],b[M]; int stack[20],top; void Add(int x,int y) { table[++tot].to=y; table[tot].next=head[x]; head[x]=tot; } void DFS1(int x,int from) { static bool v[M]; int i; v[x]=1; for(i=head[x];i;i=table[i].next) { if(table[i].to==from) continue; if(!v[table[i].to]) DFS1(table[i].to,x); else if(!~a[i>>1]) { a[i>>1]=rand(); b[table[i].to]^=a[i>>1]; b[x]^=a[i>>1]; } } } void DFS2(int x,int from) { static bool v[M]; int i; v[x]=1; for(i=head[x];i;i=table[i].next) if(!v[table[i].to]) { DFS2(table[i].to,x); a[i>>1]=b[table[i].to]; b[x]^=b[table[i].to]; } } void Gauss_Elimination() { int i,j,k=0; for(j=1<<30;j;j>>=1) { for(i=k+1;i<=top;i++) if(stack[i]&j) break; if(i==top+1) continue; swap(stack[i],stack[++k]); for(i=1;i<=top;i++) if(stack[i]&j&&i!=k) stack[i]^=stack[k]; } } int main() { srand(19980402); int i,x,y,k; cin>>n>>m; for(i=1;i<=m;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x); memset(a,-1,sizeof a); DFS1(1,0); DFS2(1,0); cin>>q; for(i=1;i<=q;i++) { scanf("%d",&k);top=0; for(;k;k--) scanf("%d",&x),stack[++top]=a[x^last_ans]; Gauss_Elimination(); last_ans+=(bool)stack[top]; printf("%s\n",stack[top]?"Connected":"Disconnected"); } }
BZOJ 3569 DZY Loves Chinese II 高斯消元
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。