首页 > 代码库 > BZOJ3569 DZY Loves Chinese II
BZOJ3569 DZY Loves Chinese II
题目链接:BZOJ3569
正解:其他+线性基
解题报告:
考虑先构出一棵原图的生成树,对于每条非树边$rand$一个权值,每条树边的权值设为覆盖(或者说跨越?)了这条边的边权异或和,
那么每次如果导致图不连通,当且仅当一条树边被删除且覆盖了这条树边的所有边都被删除了,这种情况下这些边的权值异或起来为$0$。
问题转化为给定边中是否存在若干个权值异或起来为$0$,这个用线性基做一下,每次插入线性基的时候$check$一下最后权值是否为$0$,如果为$0$就说明存在。
对于边权的预处理$dfs$两遍就好了。
//It is made by ljh2000 //有志者,事竟成,破釜沉舟,百二秦关终属楚;苦心人,天不负,卧薪尝胆,三千越甲可吞吴。 #include <algorithm> #include <iostream> #include <cstring> #include <vector> #include <cstdio> #include <string> #include <queue> #include <cmath> #include <ctime> #define lc root<<1 #define rc root<<1|1 #define SS 1000000000 #define rep(i,j,k) for(int i=j;i<=k;i++) #define reg(i,x) for(int i=first[x];i;i=next[i]) using namespace std; typedef long long LL; const int MAXN = 400011; const int MAXM = 1000011; int n,m,Q,ecnt,first[MAXN],next[MAXM],to[MAXM],val[MAXN],ans,father[MAXN],a[45]; bool vis[MAXN],use[MAXM]; struct edge{ int x,y,val; }e[MAXM]; inline void link(int x,int y){ next[++ecnt]=first[x]; first[x]=ecnt; to[ecnt]=y; } inline int getint(){ int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar(); if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w; } inline void dfs(int x,int fa){ vis[x]=1; for(int i=first[x];i;i=next[i]) { int v=to[i]; if(v==fa) continue; if(vis[v]) continue; use[i>>1]=1; father[v]=x; dfs(v,x); } } inline void dfs2(int x,int fa){ for(int i=first[x];i;i=next[i]) { int v=to[i]; if(father[v]!=x) continue; dfs2(v,x); e[i>>1].val^=val[v]; val[x]^=val[v]; } } inline void work(){ srand(20000605); n=getint(); m=getint(); ecnt=1; int x,y,k; bool ok; for(int i=1;i<=m;i++) { e[i].x=x=getint(); e[i].y=y=getint(); link(x,y); link(y,x); } dfs(1,0); for(int i=1;i<=m;i++) if(!use[i]) { x=rand()%SS+1; e[i].val=x; val[e[i].x]^=x; val[e[i].y]^=x; } dfs2(1,0); Q=getint(); while(Q--) { k=getint(); memset(a,0,sizeof(a)); ok=true; for(int i=1;i<=k;i++) { x=getint(); x^=ans; x=e[x].val; for(int j=30;j>=0;j--) { if(! ((x>>j)&1) ) continue; if(!a[j]) { a[j]=x; break; } x^=a[j]; } if(x==0) ok=false; } if(!ok) { puts("Disconnected"); } else { puts("Connected"); ans++; } } } int main() { #ifndef ONLINE_JUDGE freopen("3569.in","r",stdin); freopen("3569.out","w",stdout); #endif work(); return 0; } //有志者,事竟成,破釜沉舟,百二秦关终属楚;苦心人,天不负,卧薪尝胆,三千越甲可吞吴。
BZOJ3569 DZY Loves Chinese II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。