CF776D The Door Problem[2-SAT]

对于一扇门，如果是关的，那么他必须使用其中一个开关开开来，如果是开的，要么使用两个开关，要么啥都不做。这样，每扇门恰好对应两种状态，要选一个。

考虑用2-SAT模型解决。连边的话是对于一个机关，所有他控制的门都应该一起选（具体地说，对于一扇关闭的门，这个机关是他的第几个机关，就是哪个状态，如果是开着的，必须对应使用开关两次的状态），所以这些状态点互相连双向边。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define mst(x) memset(x,0,sizeof x)
#define dbg(x) cerr << #x << " = " << x <<endl
#define dbg2(x,y) cerr<< #x <<" = "<< x <<"  "<< #y <<" = "<< y <<endl
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
template<typename T>inline T _min(T A,T B){return A<B?A:B;}
template<typename T>inline T _max(T A,T B){return A>B?A:B;}
template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,1):0;}
template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,1):0;}
template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}
template<typename T>inline T read(T&x){
    x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1;
    while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x;
}
const int N=2e5+7;
struct thxorz{
    int head[N],to[N<<2],nxt[N<<2],tot;
    inline void link(int x,int y){
        to[++tot]=y,nxt[tot]=head[x],head[x]=tot;
        to[++tot]=x,nxt[tot]=head[y],head[y]=tot;
    }
}G;
int n,m;
int sta[N],vis[N],lock[N];
#define y G.to[j]
int dfn[N],low[N],stk[N],instk[N],Top,tim,scc,bel[N];
void tarjan(int x){
    dfn[x]=low[x]=++tim,stk[++Top]=x,instk[x]=1;
    for(register int j=G.head[x];j;j=G.nxt[j]){
        if(!dfn[y])tarjan(y),MIN(low[x],low[y]);
        else if(instk[y])MIN(low[x],dfn[y]);
    }
    if(dfn[x]==low[x]){
        int tmp;++scc;//dbg(scc);
        do instk[tmp=stk[Top--]]=0,bel[tmp]=scc;while(tmp^x);
    }
}
#undef y
int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);
    read(n),read(m);
    for(register int i=1;i<=n;++i)read(sta[i]);
    for(register int i=1,k;i<=m;++i){
        read(k);
        for(register int j=1,x,las=0;j<=k;++j,las=x){
            lock[j]=read(x);
            if(las){
                if(sta[x])sta[las]?(G.link(x,las),G.link(x+n,las+n)):(G.link(x,las+vis[las]*n),G.link(x+n,las+(1-vis[las])*n));
                else sta[las]?(G.link(x+vis[x]*n,las),G.link(x+(1-vis[x])*n,las+n)):(G.link(x+vis[x]*n,las+vis[las]*n),G.link(x+(1-vis[x])*n,las+(1-vis[las])*n));
            }
        }
        for(register int j=1;j<=k;++j)++vis[lock[j]];
    }
    for(register int i=1;i<=n<<1;++i)if(!dfn[i])tarjan(i);
    for(register int i=1;i<=n;++i)if(bel[i]==bel[i+n]){puts("NO");return 0;}
    puts("YES");return 0;
}

View Code

注意要连反向边。。我忘连了所以挂了一次。。

总结：主要在于转化模型。。看到2数字要敏感。。把每种个体转化为对应的01状态。。