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

关于 2-SAT 的小总结，希望能帮助大家

Update in 2020.9.11 改正了代码中的一些错误

也可以到我的 blog 去看哦~

2-SAT 问题：

有 n 个变量，每一个变量都是 bool 类型的，除了这 n 个变量以外，我们还有 m 个关系表达式，关系表达式差不多是这样的：

问给出 $m$ 个关系表达式后，能否给这 $n$ 个变量找出一个赋值的方法，使得满足所有的表达式； ### 建边方式： 核心问题只需要考虑有没有解； 对于每个变量都只有两种取值：$0 / 1$，那么对于每个点，我们把每个变量拆成 $true$ 点和 $false$ 点； 假如我们有一个关系：$x_1$ & $x_2 = false$； **说明 $x_1$ 和 $x_2$ 中一定有一个为 $false$；** 那么我们可以从 $x_1$ 的 $true$ 连向 $x_2$ 的 $false$，从 $x_2$ 的 $true$ 连向 $x_1$ 的 $false$；  **要注意只有关系明确的时候才能建边；** 解释一下为什么这么连边： 如果 $x_1$ 的值为 $true$ ，那么如果我们 $x_2$ 的值再为 $true$ 的话，就不满足 “ $x_1$ & $x_2 = false$ ” 这个式子了，所以如果 $x_1$ 为 $true$ 的话是能明确推出 $x_2$ 为 $false$ 的； 我们可以从 $x_2$ 的 $flase$ 向 $x_1$ 的 $true$ 连边吗？这样也能满足关系式； 显然不能，因为如果 $x_2$ 为 $false$ 的话，$x_1$ 为 $true$ 或 $ false$ 都是可以的，这不是明确的关系，我们不能建边； 所以一般的建边方式为： 若 “ $x_a = p$ 或 $x_b = q$ ” 中至少有一个满足，那么我们建两条有向边： $x_a ($¬$p) -> x_b (q) x_b ($¬$q) -> x_a (p)

可以简单总结为：其中一个不成立则另一个一定成立（这是明确的关系）；

如果一个变量必须等于 true，那么我们从这个点的 false 连向这个点的 true，表示我们从 false 走也会走到 true，也就是说只能等于 true；

至于建边的时候怎么给点编号嘛，自定义喽，不过我建议大家这样编号（下面的代码都是这么编号的）：

这样的话对于一个变量 k，编号为 k 的点代表了这个变量的 false 点，编号为 k+n 的点代表了这个变量的 true 点；

判解方式： 这么判断是否有解？

无解的情况：某一个变量的 false 能走到 true，从 true 也能走到 false，也就是说，某一个变量的两个取值在同一个强连通分量内的话，就说明无解。

求强联通分量的话常用的方法是 Tarjan 。

否则就是有解的情况，然后它一般让你输出一个给所有变量赋值的方法，使其满足所有的关系式；

那么怎么给变量赋值呢？我们来看一个图：

我们发现，从 x_1 的 false 出发会走到 x_1 的 true ，也就是说 x_1 现在只能等于 true 了；同理从 x_2 的 true 出发能走到 x_2 的 flase，说明 x_2 只能等于 flase；

解释一下吧：

如果我们不将 x_1 赋值为 true，而是赋值为 false，那会发生什么呢？

由 x_1 的 false 是能明确推出 x_2 是为 true 的，但是又有 x_2 的 true 能明确推出 x_1 为 true，这与刚刚我们将 x_1 赋值为 false 是相矛盾的；（你也可以这么理解：假如你在解方程，实在是解不出来了，你就来了个特殊值法，将 x 代入 1 试试看，结果解出来等式不成立，就说明 x ≠ 1）；

有了这个性质，就说明在有解的情况下，一个变量的两个取值是有前后推导关系的，也就是一个取值直接或间接的指向了另一个取值；

我们所要选的就是被指向的这个取值，不然会产生像上例那样的矛盾；

在拓扑序上的表现为：我们要在两种取值中选择拓扑序较大的那个值；

所以我们接下来要：缩点 + 拓扑 + 染色

其实我们在 Tarjan 的时候就已经求出了强联通分量的拓扑序了，只不过是反序；

（以我的理解是拓扑序越大的点在一棵树上是越靠近叶节点的，然后越靠近叶节点的那些节点在 Tarjan 的时候是越早被缩点的，所以拓扑序越大的点其所在强联通分量编号越小）

那么我们只要取两个取值中强联通分量编号较小的所对应的值就可以了；（这是保证不会错的，因为有时候两个值取哪个都行）

上代码喽：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
long long read()
{
    char ch=getchar();
    long long a=0,x=1;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') x=-x;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        a=(a<<1)+(a<<3)+(ch-'0');
        ch=getchar();
    }
    return a*x;
}
const int N=4e6+5;
int n,m,a,b,x,y,tim,top,edge_sum,scc_sum;
int dfn[N],low[N],st[N],vis[N],scc[N],head[N];
struct node
{
    int to,next;
}A[N];
void add(int from,int to)
{
    edge_sum++;
    A[edge_sum].next=head[from];
    A[edge_sum].to=to;
    head[from]=edge_sum;
}
void tarjan(int u)
{
    dfn[u]=low[u]=++tim;
    st[++top]=u;
    vis[u]=1;
    for(int i=head[u];i;i=A[i].next)
    {
        int v=A[i].to;
        if(!dfn[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])
    {
        scc_sum++;
        while(st[top]!=u)
        {
            scc[st[top]]=scc_sum;
            vis[st[top]]=0;
            top--;
        }
        scc[st[top]]=scc_sum;
        vis[st[top]]=0;
        top--;
    }
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        a=read();x=read();  //第a个数为x或第b个数为y 
        b=read();y=read();
        if(x==0&&y==0)      //"如果第a个数为0或第b个数为0"至少满足其一 
        {
            add(a+n,b);     //a=1则b=0 
            add(b+n,a);     //b=1则a=0 
        }
        if(x==0&&y==1)      //"如果第a个数为0或第b个数为1"至少满足其一 
        {
            add(a+n,b+n);   //a=1则b=1 
            add(b,a);       //b=0则a=0 
        }
        if(x==1&&y==0)      //"如果第a个数为1或第b个数为0"至少满足其一
        {
            add(a,b);       //a=0则b=0 
            add(b+n,a+n);   //b=1则a=1 
        }
        if(x==1&&y==1)      //"如果第a个数为1或第b个数为1"至少满足其一
        {
            add(a,b+n);     //a=0则b=1 
            add(b,a+n);     //b=0则a=1 
        }
    }
    for(int i=1;i<=2*n;i++) //对每个变量的每种取值进行tarjan 
    {
        if(!dfn[i]) tarjan(i);
    }
    for(int i=1;i<=n;i++)   //判断无解的情况 
    { 
        if(scc[i]==scc[i+n]) //同一变量的两种取值在同一强联通分量里,说明无解 
        {
            printf("IMPOSSIBLE\n");
            return 0;
        }
    }
    printf("POSSIBLE\n");   //否则就是有解 
    for(int i=1;i<=n;i++)
    {
        if(scc[i]>scc[i+n]) printf("1 ");  //强联通分量编号越小 -> 拓扑序越大 -> 越优 
        else printf("0 ");
    }
    return 0;
}

还有一个几乎和模板题一样的水题，双倍经验，双倍欢乐qwq！

P4171 [JSOI2010]满汉全席

谢谢大家的观看，觉得不错的点个赞呗(((o(*ﾟ▽ﾟ*)o)))

感谢 Chinesezjc 提供的 hack 数据，数据如下：

2 5
2 0 1 1
2 1 2 1
2 0 2 0
1 0 1 1
1 1 1 0

原先代码的问题是 if(v==fa) continue; 这一语句导致了缩点过程中若两点间相互连了两条有向边，原先代码是无法将两点判断在同一个连通块内的，所以无法通过 hack 数据。因此删掉之后就可以通过 hack 数据了。