学习资料

• 2-SAT - OI Wiki
• 题解 P4782 【【模板】2-SAT 问题】 - Anguei 的博客
• 题解 P4782 【模板】2-SAT 问题 - 暗ざ之殇 的博客 这篇blog讲了变量为什么要按照拓扑序取值

主要用来解决适应性问题是否能满足及变量的取值问题。

例题 P4782 【模板】2-SAT 问题

类似种类并查集建立满足的关系后跑 tarjan 缩点，如果发现条件不自洽则无解。有解则拓扑序小的为真，但由于tarjan求得的是反拓扑序，所以不等号要反向。

Code

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <algorithm>
#include <cmath>

using namespace std;

const int N=1e6+10;
int n,m,scc[N << 1],sc,low[N << 1],dfn[N << 1],idx,fir[N << 1],tot,sta[N << 1],top;
bool in[N << 1];
struct edge {int to,nex;} e[N << 1];
inline void add(int u,int v) {e[++tot]=(edge) {v,fir[u]}; fir[u]=tot; return ;}

void tarjan(int u)
{
    int v;
    dfn[u]=low[u]=++idx;
    sta[++top]=u; in[u]=true;
    for(int i=fir[u];i;i=e[i].nex)
        if(!dfn[v=e[i].to]) {tarjan(v); low[u]=min(low[u],low[v]);}
        else if(in[v]) low[u]=min(low[u],dfn[v]);
    if(dfn[u] == low[u])
    {
        sc++;
        while(top)
        {
            scc[v=sta[top--]]=sc;
            in[v]=false;
            if(u == v) break ;
        }
    }
    return ;
}

int main()
{
//  freopen("work.in","r",stdin); freopen("work.out","w",stdout);
    int u,v,a,b;
    scanf("%d%d",&n,&m);
    while(m--)
    {
        scanf("%d%d%d%d",&u,&a,&v,&b);
        add(u+n*a,v+n*(b^1)); add(v+n*b,u+n*(a^1));//位运算建图，一个不成立，另一个必成立
    }
    for(int i=1;i<=n<<1;i++) if(!dfn[i]) tarjan(i);
    bool ans=true;
    for(int i=1;i<=n && ans;i++)
        if(scc[i] == scc[i+n]) {puts("IMPOSSIBLE"); ans^=1;}//不自洽
    if(ans)
    {
        puts("POSSIBLE");
        for(int i=1;i<=n;i++) printf("%d ",scc[i] < scc[i+n]);//按拓扑序来确定取值
    }
//  fclose(stdin); fclose(stdout);
    return 0;
}

注意这里我们的数组要开双倍。

练习

P4171 [JSOI2010] 满汉全席

基本和模板一样，注意一下输入格式就行。

P5782 [POI2001] 和平委员会 题解