2-SAT

2-SAT

一个2-SAT的经典例题,每个点有两种选择,给出每个点的关系,比如说选择i必须选择j,选择i不能选择j等,问是否有解。

2-SAT的想法就是将每个点拆成两个,然后连边有向边。

如果i \to j有边表示选择i必须选择j。

如果当前点i * 2i * 2+1都被选择了,说明无解。因为一个点只能有一个值。

那么怎么建图呢?

a[i]表示点i的状态(0,1)。i * 2表示a[i]=0,i * 2+1表示a[i]=1。

a[i]&&a[j]==0

如果a[i]为1那么a[j]必须为0。

如果a[j]为1那么a[i]必须为0。

,i * 2+1 \to j * 2,j * 2+1 \to j * 2

a[i]||a[j]==1

如果a[i]为0那么a[j]必须为1。

如果a[j]为0那么a[i]必须为1。

,i * 2\to j * 2+1,j * 2\to i * 2+1

a[i]=0

那么就将i * 2+1 \to i * 2

a[i]=1

i * 2 \to i * 2+1

暴力做法

每次DFS去判断是否有解,然后撤回标记,理论复杂度O(n*m),但是洛谷2-SAT模板题,我跑的比Tarjan快,首次登上榜首,然后第二天就被超了QAQ。

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
const int MAXN=1e6+5;
int n,m,Top,Stk[MAXN<<1];
bool vis[MAXN<<1];
struct Edge{
    int tot,lnk[MAXN<<1],nxt[MAXN<<2],son[MAXN<<2];
    void Add(int x,int y){nxt[++tot]=lnk[x];son[tot]=y;lnk[x]=tot;}
}E;
int read(){
    int ret=0;char ch=getchar();bool f=1;
    for(;!isdigit(ch);ch=getchar()) f^=!(ch^'-');
    for(; isdigit(ch);ch=getchar()) ret=(ret<<3)+(ret<<1)+ch-48;
    return f?ret:-ret;
}
bool DFS(int x){
    if(vis[x^1]) return 0;
    if(vis[x]) return 1;
    Stk[++Top]=x;vis[x]=1;
    for(int j=E.lnk[x];j;j=E.nxt[j]) if(!DFS(E.son[j])) return 0;
    return 1;
}
bool Solve(){
    for(int i=0;i<n;i++)
    if(!vis[i<<1]&&!vis[i<<1|1]){
        Top=0;
        if(!DFS(i<<1)){
            while(Top) vis[Stk[Top--]]=0;
            if(!DFS(i<<1|1)) return 0;
        }
    }
    return 1;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("P4782.in","r",stdin);
    freopen("P4782.out","w",stdout);
    #endif
    n=read(),m=read();
    for(int i=1;i<=m;i++){
        int x=read()-1,a=read(),y=read()-1,b=read();
        x=(x<<1)+a;y=(y<<1)+b;
        E.Add(x^1,y),E.Add(y^1,x);
    }
    if(!Solve()) printf("IMPOSSIBLE\n");
    else{
        printf("POSSIBLE\n");
        for(int i=0;i<n-1;i++) if(vis[i<<1]) printf("0 ");else printf("1 ");
        if(vis[(n-1)<<1]) printf("0\n");else printf("1\n");
    }
    return 0;
} 

Tarjan

作者正在学习中。。。。

发表评论

开始在上面输入您的搜索词,然后按回车进行搜索。按ESC取消。

返回顶部