2-SAT

l1ng21y12026 · 2024-08-06 15:38:41 · 算法·理论

2-SAT

（零）引入

2-SAT 算法用于求解逻辑方程组，如：

有 n 个01变量 x_i，给出 m 组关系：x_i=a 或 x_j=b，其中 a,b\in\{0,1\}；

求一组解，使得满足所有条件。

（一）算法简介

将限制转化为图，比如对于：x=1 或 y=1，若 x=0，则一定 y=1；若 y=0，则一定 x=1；

其实就是 a\implies b 等价于 \neg a\vee b。即 a\implies b 为假当且仅当 a 为真、b 为假。

即 a\vee b 可以拆分为 \neg a\implies b,\neg b\implies a。

于是对点 x 开两个点 x,x+n 表示取值 1/0，于是可以对于上面描述建边；

观察发现：

• 在同一个强连通分量里的点取值相同：当 x,x+n 在同一个强连通分量里，无解。

使用 tarjan 缩点，染的颜色是倒拓扑序；于是若 color[x]<color[x+n] 则 x=1；

时间复杂度为 O(n+m)；

#include<bits/stdc++.h>
#define rg register int
#define fo(i,l,r) for(rg i=l;i<=r;i++)
#define dfo(i,r,l) for(rg i=r;i>=l;i--)
#define frein freopen("in.txt","r",stdin);
#define freout freopen("out.txt","w",stdout);
#define fre(p) freopen(#p".in","r",stdin),freopen(#p".out","w",stdout);
#define outa(l,r,a) {fo(i,l,r)cout<<a[i]<<" ";cout<<"\n";}
#define outm(l1,r1,l2,r2,a) {fo(i,l1,r1){fo(j,l2,r2)cout<<a[i][j]<<" ";cout<<"\n";}cout<<"\n";}
#define BZ cout<<"----------------\n";
#define ll long long
using namespace std;
void rd(int &x){
    int v(0),op(1);
    register char c=getchar();
    while(c<'0'||'9'<c)op=c=='-'?-1:1,c=getchar();
    while('0'<=c&&c<='9')v=(v<<1)+(v<<3)+(c^48),c=getchar();
    x=v*op;
}
void no(){printf("IMPOSSIBLE");exit(0);}
const int N=2e6+5;
int n,m,x,px,y,py;
int sum,to[N<<1],nex[N<<1],hd[N];
void add(int x,int y){to[++sum]=y,nex[sum]=hd[x],hd[x]=sum;}
int cnt,dfn[N],low[N],st[N],l,col[N],cl;bool bz[N];
void tarjan(int x){
    dfn[x]=low[x]=++cnt,bz[x]=1,st[++l]=x;
    for(rg i=hd[x];i;i=nex[i]){
        if(dfn[to[i]]==0)tarjan(to[i]),low[x]=min(low[x],low[to[i]]);
        if(bz[to[i]]==1)low[x]=min(low[x],dfn[to[i]]);
    }
    if(dfn[x]==low[x]){
        ++cl;
        do{col[st[l]]=cl,bz[st[l--]]=0;}while(st[l+1]!=x);
    }
}
int main(){
    rd(n),rd(m);
    fo(i,1,m){
        rd(x),rd(px),rd(y),rd(py);
        if(px==1&&py==1)add(x+n,y),add(y+n,x);
        if(px==1&&py==0)add(x+n,y+n),add(y,x);
        if(px==0&&py==1)add(x,y),add(y+n,x+n);
        if(px==0&&py==0)add(x,y+n),add(y,x+n);
    }
    fo(i,1,2*n)if(dfn[i]==0)tarjan(i);
    fo(i,1,n)if(col[i]==col[i+n])no();
    printf("POSSIBLE\n");
    fo(i,1,n)printf("%d ",(col[i]<col[i+n]));
    return 0;
}

（二）应用与例题

Gmoj.8097. 不平衡的对战

题面