【模板】2-SAT 问题

洛咕

题意:有n个布尔变量\(x_1\)~\(x_n\)，另有m个需要满足的条件，每个条件的形式都是“\(x_i\)为\(true/false\)或\(x_j\)为\(true/false\)”.比如“\(x_1\)为真或\(x_3\)为假”、“\(x_7\)为假或\(x_2\)为假”.\(2-SAT\) 问题的目标是给每个变量赋值使得所有条件得到满足.\(n,m<=100000\).

分析:\(2-SAT\)一般注意两个点:建图和输出方案.

对于建图,一定是要满足"若p,则必须q"时才能连边.举个例子.如果\(x_i=1\)或者\(x_j=1\),则若\(x_i=0\),则\(x_j\)必须\(=1\),所以建有向边\(i->j+n\),同理若\(x_j=0\),则\(x_i\)必须\(=1\),所以建有向边\(j->i+n\).都按这样来考虑就行.

然后输出方案的话背一下这个模板就好.

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=2e6+5;
int tot,head[N],nxt[N],to[N],opp[N],val[N];
int tim,top,num,dfn[N],low[N],st[N],color[N],belong[N];
inline void add(int a,int b){
    nxt[++tot]=head[a];head[a]=tot;to[tot]=b;
}
inline void tarjan(int u){
    dfn[u]=low[u]=++tim;st[++top]=u;
    for(int i=head[u];i;i=nxt[i]){
        int v=to[i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!color[v])low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u]){
        color[u]=++num;
        while(st[top]!=u){
            color[st[top]]=num;
            --top;
        }
        --top;
    }
}
int main(){
    int n=read(),m=read();
    for(int i=1;i<=m;++i){
        int a=read(),b=read(),c=read(),d=read();
        if(!b&&!d)add(a+n,c),add(c+n,a);
        if(!b&&d)add(a+n,c+n),add(c,a);
        if(b&&!d)add(a,c),add(c+n,a+n);
        if(b&&d)add(a,c+n),add(c,a+n);
    }
    for(int i=1;i<=2*n;++i)if(!dfn[i])tarjan(i);
    for(int i=1;i<=n;++i){
        if(color[i]==color[i+n]){
            puts("IMPOSSIBLE");return 0;
        }
        opp[i]=n+i;opp[n+i]=i;
    }
    puts("POSSIBLE");
    for(int i=1;i<=2*n;++i)
        val[i]=color[i]>color[opp[i]];
    for(int i=1;i<=n;++i){
        if(!val[i])printf("0 ");
        else printf("1 ");
    }
    printf("\n");
    return 0;
}