2-SAT

发表于 更新于 分类于

2-SAT

SAT 问题定义

SAT的全称：satisfiability（可满足性）

有一个由N个布尔值组成的序列A，给出一些限制关系，比如A[x] AND A[y]=0、A[x] OR A[y] OR A[z]=1等，要确定A[0..N-1]的值，使得其满足所有限制关系，这就是SAT问题。

2-SAT 特殊点

特别的，若每种限制关系中最多只对两个元素进行限制，则称为2-SAT问题。

2-SAT问题是有多项式解法的，而3-SAT就是npc问题。

总结：

限制条件针对两个元素

解法：强连通分量

判断是否有解

建立2N个点的有向图，不妨设：

i点表示\(x_i\)=False
i’点表示\(x_i\)=True

一条u->v的有向边表示如果选择了u，那么一定要选择v。

2-SAT有解当且仅当对于任意一个\(\mathrm{i}\) (\(1 \leq \mathrm{i} \leq \mathrm{N}\)) 不能出现如下情况：在这个有向图中从\(\mathrm{i}\)点出发可以到达\(\mathrm{i}'\)点，且从\(\mathrm{i}'\)点出发可以到达\(\mathrm{i}\)点。

如何实现上面的判断？

即矛盾需要取消使用（互相可以证明），矛盾

如何实现上面的判断？

判断i和i’是否位于同一强连通分量即可！使用Kosaraju算法可以在线性时间内求出强连通分量。

思路

输出可行方案

如果从\(\mathrm{i}\)点出发可以到达\(\mathrm{i}'\)点，则选了\(\mathrm{i}\)会导致选\(\mathrm{i}'\)，矛盾，因此只能选\(\mathrm{i}'\)。

Kosaraju算法在求强连通分量的时候顺带求出了一个遍历顺序\(\mathrm{q}[1], \mathrm{q}[2], \dots, \mathrm{q}[\mathrm{cnt}]\)；只需要比较\(\mathrm{i}\)和\(\mathrm{i}'\)所属强连通分量在\(\mathrm{q}\)中位置的前后关系即可构造出可行方案。

思考：具体怎么选？

一元限制建图

一元限制的构图方法

  • 限制：\(x_i\)=True
  • 连边\(i \to i'\)
  • 表示如果\(i\)选了False那么\(i\)必须要是True
  • 与\(i\)只能选一个True或者False矛盾，强迫\(i\)只能是True

二元限制构图

二元限制的构图方法

  • 一条边u→v的含义：若u则v。
  • 命题“若u则v”的逆否命题为“若非v则非u”。
  • 命题与其逆否命题等价。
  • 例子：“若x是4的倍数，则x是偶数”的逆否命题为“若x不是偶数，则x不是4的倍数”。

OR TRUE：

  • 限制：u or v=True
  • 若u为假，则v为真：连边u->v’。
  • 若v为假，则u为真：连边v->u’。

AND FALSE

  • 限制：u and v=False
  • 若u为真，则v为假：连边\(u' \to v\)。
  • 若v为真，则u为假：连边\(\overline{v}' \to \overline{u}\)。

AND TRUE

  • 限制：u and v=True
  • u为真：连边u→u’。
  • v为真：连边v→v’。

!=(共4边)

  • 限制：\(u != v\)
  • 若\(u\)为真，则\(v\)为假：连边\(u' \to v\)。
  • 若\(u\)为假，则\(v\)为真：连边\(u \to v'\)。
  • 若\(v\)为真，则\(u\)为假：连边\(v' \to u\)。
  • 若\(v\)为假，则\(u\)为真：连边\(v \to u'\)。

== (共4边)

  • 限制：\(u==v\)
  • 若\(u\)为真，则\(v\)为真：连边\(u' \to v'\)。
  • 若\(u\)为假，则\(v\)为假：连边\(u \to v\)。
  • 若\(v\)为真，则\(u\)为真：连边\(v' \to u'\)。
  • 若\(v\)为假，则\(u\)为假：连边\(v \to u\)。

eg-1聚会

  • 有n对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有1人可以列席。
  • 在2n个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），主办方希望有矛盾的2个人不同时出现在聚会上。
  • 问有没有可能会有n个人同时列席？

解题代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
#define ll long long

int n,m;
struct node{
    int to;
    int next;
};
node edge[1000010];
int head[2010];
int cnt;
int vis[2010];
int u;
int p[2010];
int f[2010];
vector<int> v;

int r(int x){
    if(x>=n){
        return x-n;
    }
    return x+n;
}

void addedge(int from,int to){
    edge[++cnt].to=to ;
    edge[cnt].next=head[from];
    head[from]=cnt;
    return;
}

void fdfs(int x){
    vis[x]=1;
    for(int k=head[x];k!=0;k=edge[k].next){
        if(!vis[edge[k].to]){
            fdfs(edge[k].to);
        }
    }
    p[--u]=x;
    return ;
}

void dfs(int x,int fa){
    vis[x]=0;
    f[x]=fa;
    for(int k=head[x];k!=0;k=edge[k].next){
        if(vis[edge[k].to]){
            dfs(edge[k].to,fa);
        }
    }
    return ;
}

int main(){
    while(cin>>n>>m){
        memset(vis,0,sizeof(vis));
        memset(head,0,sizeof(head));
        v.clear();
        cnt=0;
        u=2*n;
        for(int i=0;i<m;i++){
            int a1,a2,c1,c2;
            scanf("%d%d%d%d",&a1,&a2,&c1,&c2);
            if(c1){
                a1=r(a1);
            }
            if(c2){
                a2=r(a2);
            }
            v.push_back(a1);
            v.push_back(a2);
            addedge(a1,r(a2));
            addedge(a2,r(a1));
        }
        for(int i=0;i<2*n;i++){
            if(!vis[i]){
                fdfs(i);
            }
        }
        // //test:p
        // for(int i=0;i<2*n;i++){
        //  cout<<p[i]<<" ";
        // }
        // cout<<endl;

        cnt=0;
        memset(head,0,sizeof(head));
        for(int i=0;i<m;i++){
            int a1=v[i*2];
            int a2=v[i*2+1];
            addedge(r(a1),a2);
            addedge(r(a2),a1);
        }
        for(int i=0;i<2*n;i++){
            if(vis[p[i]]){
                dfs(p[i],p[i]);
            }
        }
        // //testf;
        // for(int i=0;i<2*n;i++){
        //  cout<<f[i]<<" ";
        // }
        // cout<<endl;

        bool flag=true;
        for(int i=0;i<n;i++){
            if(f[i]==f[r(i)]){
                flag=false;
                break;
            }
        }
        if(flag){
            printf("YES\n");
        }
        else{
            printf("NO\n");
        }
    }

    return 0;
}

第一步：抽象成图论模型

  • 建立2n个点的有向图，i点表示第i对夫妻是丈夫到场，i’点表示是妻子到场。
  • 如果A和B矛盾，则可以表示为“若A则非B”、“若B则非A”。

强连通分量求出后的处理：

bool ans = 1;
for (int i = 0; i < N; i++) {
    if (f[i] == f[trans(i)]) {
        ans = 0;
        break;
    }
}
if (ans) {
    cout << "YES" << endl;
}
else {
    cout << "NO" << endl;
}

eg-2队

  • T个3人队伍，每个队伍有一个队长。
  • 每个队伍要么队长回家，剩下两人留校；要么队长留校，剩下两人回家。
  • 给定M条限制，每条限制指定两个人A和B，要求A和B不能同时留校。
  • 判断是否有合法方案。

解决：

  • 建立6T个点的有向图，i点表示第i个人留校，i’点表示第i个人回家。

  • 对于每个队伍X,Y,Z，其中X为队长。

  • X和Y的选择不同，按照X!=Y连边。

  • X和Z的选择不同，按照X!=Z连边。

  • Y和Z的选择相同，按照Y==Z连边。

  • 对于每条限制A,B，两人不能同时留校。

  • 若A留校，则B回家：\(A \to B'\)

  • 若B留校，则A回家：\(B \to A'\)

合理建边

解题代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long

int t,m,n;
struct node{
    int to;
    int next;
};
node edge[400010];
node fedge[400010];
int head[6010];
int fhead[6010];
int p[6010];
int f[6010];
int cnt;
int fcnt;
int u;
bool vis[6010];

int r(int x){
    if(x>=3*t){
        return x-3*t;
    }
    return x+3*t;
}

void addedge(int from,int to){
    edge[++cnt].to=to;
    edge[cnt].next=head[from];
    head[from]=cnt;
    return ;
}

void addfedge(int from,int to){
    fedge[++fcnt].to=to;
    fedge[fcnt].next=fhead[from];
    fhead[from]=fcnt;
    return ;
}

void fdfs(int x){
    vis[x]=1;
    for(int k=fhead[x];k!=0;k=fedge[k].next){
        if(!vis[fedge[k].to]){
            fdfs(fedge[k].to);
        }
    }
    p[--u]=x;
    return ;
}

void addnoequal(int p1,int p2){
    addedge(p1,r(p2));
    addedge(r(p1),p2);
    addedge(p2,r(p1));
    addedge(r(p2),p1);
    addfedge(p1,r(p2));
    addfedge(r(p1),p2);
    addfedge(p2,r(p1));
    addfedge(r(p2),p1);
    return ;
}

void addequal(int p1,int p2){
    addedge(p1,p2);
    addedge(p2,p1);
    addedge(r(p1),r(p2));
    addedge(r(p2),r(p1));
    addfedge(p1,p2);
    addfedge(p2,p1);
    addfedge(r(p1),r(p2));
    addfedge(r(p2),r(p1));
    return ;
}

void dfs(int x,int fa){
    vis[x]=0;
    f[x]=fa;
    for(int k=head[x];k!=0;k=edge[k].next){
        if(vis[edge[k].to]){
            dfs(edge[k].to,fa);
        }
    }
    return ;
}

int main(){
    while(cin>>t>>m){
        memset(head,0,sizeof(head));
        memset(fhead,0,sizeof(fhead));
        memset(vis,0,sizeof(vis));
        cnt=0;
        fcnt=0;
        u=6*t;
        n=6*t;
        for(int i=0;i<t;i++){
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            addnoequal(x,y);
            addnoequal(x,z);
            addequal(y,z);
        }
        for(int i=0;i<m;i++){
            int x,y;
            scanf("%d%d",&x,&y);
            addedge(x,r(y));
            addedge(y,r(x));
            addfedge(r(y),x);
            addfedge(r(x),y);
        }
        for(int i=0;i<n;i++){
            if(!vis[i]){
                fdfs(i);
            }
        }
        // //testp;
        // for(int i=0;i<n;i++){
        //  cout<<p[i]<<" ";
        // }
        // cout<<endl;

        for(int i=0;i<n;i++){
            if(vis[p[i]]){
                dfs(p[i],p[i]);
            }
        }
        // //testf;
        // for(int i=0;i<n;i++){
        //  cout<<f[i]<<" ";
        // }
        // cout<<endl;
        bool flag=true;
        for(int i=0;i<t;i++){
            if(f[i]==f[r(i)]){
                flag=false;
                break;
            }
        }
        if(flag){
            printf("yes\n");
        }
        else{
            printf("no\n");
        }
    }

    return 0;
}

小结

特别提醒

  • 1、大部分题目均是天然具有逆否命题的情况，不易出错，但是——
  • 2、务必注意某些题目需要额外建立逆否命题的边；
  • 比如，题目中告诉：如果A则B，这种情况如何建边？

需要做相关的题目（luogu，poj等）

致谢

  • 参考资料：
  • https://www.cnblogs.com/L-Excalibur/p/8504893.html
  • https://blog.sengxian.com/algorithms/2-sat