一、问题描述

以你咕的模板题为例

题目描述

有$n$个布尔变量$x_1$~$x_n$，另有$m$个需要满足的条件，每个条件的形式都是“$x_i$为true/false或$x_j$为true/false”。

比如“$x_1$为真或$x_3$为假”、“$x_7$为假或$x_2$为假”。

2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。

二、逻辑关系

这里不用太过专业的符号来说明逻辑关系，仅仅是感性说明（没错就是我菜）

设条件为大写字母A,B，非A,非B只条件的另一种取值

A或者B 等价于非A则B 和非B则A

注意到后面两个要求似乎有蜜汁对称性，而且它们都是有向的

根据后一句话，我们借助并查集扩展域的思想，把一个点的两个取值拆开，进行建图

三、建图

这里就画图举例说明吧

给出这样三个条件$(1,1)$或$(2,1)$,$(2,1)$或$(3,1)$,$(2,0)$或(3,1)$

$(x,y)$表示$x$需要取值$y$

我们把点$x$取值$0$的点编号$x$，取值$1$的点编号$x+n$

我们可以建出如下的图

有向边$(u,v)$表示如果$u$选，$v$一定选

很显然这是有解的，我们可以去$1,2,3$等点集

怎么样才会无解呢？

如果一个点的出边的点构成的集合中又出现了它自己？这样可以不选它而选另一个值啊

如果这个集合出现了另一个值呢？

好吧，这里的无解其实就是综合一下，选它的同时要选它的另一个值，选它的另一个值同时要选它

等价于两者在有向图中处于同一个环中

这样我们就可以通过tarjan求环来判断有解性了

四、构造合法方案

如果一个点没有伸出去的边，就代表它不约束别人，我们可以随便选择选或不选它

设$cho[]$，若$cho[x]==0$则代表我们选择了它，否则我们没有选择它

优先选择出度为0的点

我们可以在缩点后的图中反向建图，然后做拓扑排序

注意我们选择一个点后，要把它对应的点置不选

事实上，我们也可以没必要做这么麻烦

dfs遍历的DAG图的序列反过来其实就是反向建边的拓扑序

在tarjan中先做的点的编号就是反向建边拓扑序

那么我们直接比编号大小进行赋值就可以啦

五、参考代码

#include <cstdio>

int min(int x,int y){return x<y?x:y;}

const int N=2e6+10;

int head[N],to[N<<1],Next[N<<1],cnt,n,m;

void add(int u,int v)

{

    to[++cnt]=v;Next[cnt]=head[u];head[u]=cnt;

}

void init()

{

    scanf("%d%d",&n,&m);

    for(int i,a,j,b,k=1;k<=m;k++)

    {

        scanf("%d%d%d%d",&i,&a,&j,&b);

        add(i+(1-a)*n,j+b*n),add(j+(1-b)*n,i+a*n);

    }

}

int dfn[N],low[N],in[N],s[N],ha[N],tot,dfs_clock,n_;

void tarjan(int now)

{

    dfn[now]=low[now]=++dfs_clock;

    s[++tot]=now;

    in[now]=1;

    for(int i=head[now];i;i=Next[i])

    {

        int v=to[i];

        if(!dfn[v])

        {

            tarjan(v);

            low[now]=min(low[now],low[v]);

        }

        else if(in[v])

            low[now]=min(low[now],dfn[v]);

    }

    if(low[now]==dfn[now])

    {

        int k;++n_;

        do

        {

            k=s[tot--];

            ha[k]=n_;

            in[k]=0;

        }while(k!=now);

    }

}

void work()

{

    for(int i=1;i<=n<<1;i++) if(!dfn[i]) tarjan(i);

    for(int i=1;i<=n;i++)

        if(ha[i]==ha[i+n])

        {

            printf("IMPOSSIBLE\n");

            return;

        }

    printf("POSSIBLE\n");

    for(int i=1;i<=n;i++)

        printf("%d ",ha[i]>ha[i+n]);

}

int main()

{

    init();

    work();

    return 0;

}

2018.9.1

巴特西

2-sat 学习笔记