BZOJ3569:DZY Loves Chinese II(&&BZOJ3563) 高斯消元+构造

思路:

首先构造出原无向图的一棵生成树,然后就有一些非树边以及一些树边了吧.

给非树边随机一个unsignde long long的权值,并令每个树边的权值等于覆盖这条树边的所有非树边权值的异或和.

考虑删去哪些边之后可以使得原图不连通.

如果只删掉非树边显然是没用的.

那么我们必须删掉一条树边,以及覆盖这条树边的所有非树边!注意到这些边权值的异或和正好为0,因此问题转化为存不存在一个异或和为0的子集.于是高斯消元水.

时间复杂度\(O(n+64kq)\).

另外I可以拿一个有趣的方法水过...详情见代码.

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
 
typedef unsigned long long LLU;
 
inline LLU get(){
    LLU res=1;for(int i=1;i<=4;++i)res*=rand();return res;
}
 
#define N 100010
#define M 500010
int head[N],next[M<<1],end[M<<1];LLU f[M<<1];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
inline void make(int a,int b){addedge(a,b),addedge(b,a);}
 
int pa[N];
LLU v[N];
inline void dfs(int x){
    for(int j=head[x];j;j=next[j])if(!pa[end[j]]&&end[j]!=1)pa[end[j]]=x,dfs(end[j]);
}
inline void dfs2(int x){
    for(int j=head[x];j;j=next[j])
        if(pa[end[j]]==x)
            dfs2(end[j]),v[x]^=v[end[j]];
    for(int j=head[x];j;j=next[j])
        if(pa[end[j]]==x)
            f[(j+1)/2*2-1]=f[(j+1)/2*2]=v[end[j]];
}
 
LLU ins[64];
 
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
#endif
    int n,m;scanf("%d%d",&n,&m);register int i,j;
    int a,b;for(i=1;i<=m;++i)scanf("%d%d",&a,&b),make(a,b);
     
    dfs(1);
    LLU now;
    for(i=1;i<=n;++i)for(j=head[i];j;j=next[j])if(i!=pa[end[j]]&&pa[i]!=end[j]){
        now=get();f[(j+1)/2*2-1]^=now,f[(j+1)/2*2]^=now,v[i]^=now,v[end[j]]^=now;
    }
    dfs2(1);
     
    int lans=0,q,t,x;LLU tmp;scanf("%d",&q);
    while(q--){
        scanf("%d",&t);
        memset(ins,0,sizeof ins);
        bool ok=1;
        for(i=1;i<=t;++i){
            scanf("%d",&x),tmp=f[2*(x^=lans)];
            for(j=63;j>=0;--j)if((tmp>>j)&1){
                if(!ins[j]){ins[j]=tmp;break;}else tmp^=ins[j];
            }
            if(!tmp)ok=0;
        }
        if(ok)puts("Connected"),++lans;else puts("Disconnected");
    }
     
    return 0;
}

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 100010
#define M 500010
int head[N],next[M<<1],end[M<<1],ban[M<<1];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
inline void make(int a,int b){addedge(a,b),addedge(b,a);}
 
char s[10010];
 
int stk[16<<1],top;
 
bool vis[N];
void dfs(int x){
    vis[x]=1;for(int j=head[x];j;j=next[j])if(!ban[j]&&!vis[end[j]])dfs(end[j]);
}
 
int sav[20],num;
inline bool digit(char c){
    return c>='0'&&c<='9';
}
void get(){
    gets(s);int len=strlen(s);
    num=0;
    int tmp,i,j;
    for(i=0;i<len;){
        if(digit(s[i])){
            tmp=s[i]-'0';
            for(j=i+1;j<len&&digit(s[j]);++j)tmp=10*tmp+s[j]-'0';
            sav[++num]=tmp,i=j;
        }else++i;
    }
}
 
int lans[50010];
int main(){
    int n,m;scanf("%d%d",&n,&m);register int i,j;
    int a,b;for(i=1;i<=m;++i)scanf("%d%d",&a,&b),make(a,b);
     
    int Q;scanf("%d",&Q);gets(s);
     
    for(i=1;i<=Q;++i){
        get();
        lans[i-1]=(num-1)^sav[1];
    }
     
    for(i=1;i<Q;++i)if(lans[i]>lans[i-1])puts("Connected");else puts("Disconnected");
     
    for(i=2;i<=num;++i)sav[i]^=lans[Q-1],ban[2*sav[i]-1]=ban[2*sav[i]]=1;
    int cnt=0;for(i=1;i<=n;++i)if(!vis[i])dfs(i),++cnt;
    if(cnt==1)puts("Connected");else puts("Disconnected");
     
    return 0;
}