2-SAT

· · 算法·理论

介绍

2-SAT 是用于解决一类问题，其形式如下：

有 n 个节点，每个节点有 2 种取值，然后这些取值要满足一些性质，求合法方案。

具体地，掏出例题：P4782 【模板】2-SAT

怎么做呢？ 我们发现对于一个形如 a\ or\ b 的条件，如果 a 不成立，那么 b 必须成立，所以说 \lnot a \Rightarrow b。反之亦然。并且每个变量只有两种取值，所以考虑把一个点拆成两个点，其中 1\sim n 的点表示编号为 1\sim n 的点取值为 0，n+1\sim n\times 2 的点为 编号 1\sim n 的点取值为 1。那么如果有一个 a\Rightarrow b，那么就把 a\rightarrow b 连起来。最后得到一个有向图。

发现这个图有可能带环，所以考虑缩点。如果一个强联通分量里同时存在 i 和 i+n，那么不存在一种合法的方案。因为一个变量的一种状态可以推出其取值为另一种状态，那么这是矛盾的。

否则 i 与 i+n 肯定在这个 DAG 上有一个是拓扑序较大的，那么取值取的是拓扑序较大的那个状态表示的值，因为拓扑序较大的推不出较小的。

时间复杂度：O(n+m) ，由tarjan不难得出。

至此，我们完成了模版题。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=2e6+10;
LL n,m,bel[N],dfn[N],low[N],T,tot;
bool in[N];
stack<LL> st;
vector<LL> e[N];
void add(LL u,LL v) { e[u].push_back(v); }
void tarjan(LL u) //tarjan缩点
{
    dfn[u]=low[u]=++T;
    st.push(u); in[u]=1;
    for(auto v:e[u])
    {
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u])
    {
        ++tot;
        while(true)
        {
            LL i=st.top(); st.pop();
            in[i]=0; bel[i]=tot;
            if(i==u) break;
        }
    }
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=m;i++)
    {
        LL u,v,a,b;
        scanf("%lld%lld%lld%lld",&u,&a,&v,&b);
        add(v+(b^1)*n,u+a*n); //如果一方不成立，则可以推出另一方成立
        add(u+(a^1)*n,v+b*n); //注意要建单项边
    }
    for(int i=1;i<=2*n;i++)
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<=n;i++)
        if(bel[i]==bel[i+n])
            return !printf("IMPOSSIBLE"); //如果一个变量的两种状态可以互相推出来，那么不可能有解
    printf("POSSIBLE\n");
    for(int i=1;i<=n;i++)
        printf("%d ",bel[i+n]<bel[i]); //实际上不用做拓扑排序，因为tarjan是一个dfs，那么强联通分量编号小的是拓扑序大的
    return 0;
}

例题

P6378 [PA2010] Riddle

这个题发现每个点有两种状态：是或不是关键点，且要满足状态之间的关系，考虑2-SAT。

令一个点取 1 为关键点，取 0 为非关键点。对于一条边的限制，类似于模版题，是一个或的关系，自己想想怎么处理。对于同一个部分中，如果一个点取了 1，那么其他的点必须取 0，那么就是一个推出的关系。所以直接暴力连边，跑 2-SAT。

但是边数是 O(n^2) 的怎么办？发现这个是对于同一个部分中只连除自己外的节点，那么考虑对 0 的节点做一个前缀序列 pre 和后缀序列 suf，使得连向 pre_i 可以连向 1\sim i 的节点，suf 同理，那么对于 i 之前的暴力连边可以变成连向 pre_{i-1} 和 suf_{i+1} 优化，此时边数为 O(n)。具体可以看代码和画图理解。

我们称这个优化为前后缀优化建图。不仅有前后缀优化建图，还有线段树优化建图。可以自行意会，但是听老师说没怎么考。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=4e6+10;
LL n,m,k,bel[N],dfn[N],low[N],T,tot,id[N];
bool in[N];
stack<LL> st;
vector<LL> e[N];
void add(LL u,LL v) { e[u].push_back(v); }
void tarjan(LL u)
{
    dfn[u]=low[u]=++T;
    st.push(u); in[u]=1;
    for(auto v:e[u])
    {
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(in[v])
            low[u]=min(low[u],dfn[v]);
    }
    if(low[u]==dfn[u])
    {
        ++tot;
        while(true)
        {
            LL i=st.top(); st.pop();
            in[i]=0; bel[i]=tot;
            if(i==u) break;
        }
    }
}
int main()
{
    //1~n 0 n+1~n+n 1
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1;i<=m;i++)
    {
        LL u,v;
        scanf("%lld%lld",&u,&v);
        add(v,u+n);
        add(u,v+n);
    }
    for(int i=1;i<=k;i++)
    {
        LL w;
        scanf("%lld",&w);
        for(int j=1;j<=w;j++) scanf("%lld",id+j);
        for(int j=1;j<=w;j++)
        {
            if(j>1) add(id[j]+n*2,id[j-1]+n*2); //n*2+1~n*3是前缀节点，向前面连边
            if(j<w) add(id[j]+n*3,id[j+1]+n*3); //n*3+1~n*4是后缀节点
            add(id[j]+n*2,id[j]); //前后缀节点要连向对应的表示取值为0的节点
            add(id[j]+n*3,id[j]);
            if(j>1) add(id[j]+n,id[j-1]+n*2); //优化连边
            if(j<w) add(id[j]+n,id[j+1]+n*3);
        }
    }
    for(int i=1;i<=2*n;i++)
        if(!dfn[i])
            tarjan(i);
    for(int i=1;i<=n;i++)
        if(bel[i]==bel[i+n])
            return !printf("NIE");
    printf("TAK");
    return 0;
}

作业

P3825 [NOI2017] 游戏

P3513 [POI2011] KON-Conspiracy

P4171 [JSOI2010] 满汉全席

AT_abc210_f [ABC210F] Coprime Solitaire

其中 满汉全席 和板子差不多，Coprime Solitaire和例题讲的差不多，只是分出每个部分要按照质因数而已。