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

· · 题解

2-sat

$$x_{p_1}\oplus x_{p_2}\oplus x_{p_3}\cdots\oplus x_{p_k}=a$$ 其中，$a$是$0$或者$1$，而$\oplus$是某一种二元$bool$操作。 $k>2$的情况已被证明是$NP$问题，目前只能够暴力枚举来解决。 而当$k=2$时，存在$O(nm)$和$O(n+m)$两种常用做法。$O(nm)$的做法可以用来解决关于最小字典序解的问题。因为无法通过此题，所以在此只描述$O(n+m)$的算法。 因为条件是二元的，因此每个限制都只会涉及$2$个变量。这启发我们使用图论来解决这个问题。我们将每个变量都拆成$2$个，分别表示该变量$=0$和$=1$的情况。再定义边$(u,v)$表示选择$u$就必须选择$v$。那么，我们可以直接将问题转化成以下$3$种情况: (以下为了方便，用$x_{i,a}$表示第$i$个变量选择$a$的点，$(u,v)$表示$u$到$v$的边，$\otimes$表示异或) ### 1. $x_i=a$ ,则 $x_j=b

建边(x_{i,a},x_{j,b}),(x_{j,b\otimes1},x_{i,a\otimes1})

意义显然。如果x_i=a，那么x_j=b。如果x_j!=b，那么x_i!=a。

2. x_i=a 与 x_j=b 至少满足一个

建边

(x_{i,a\oplus1},x_{j,b})$,$(x_{j,b\oplus1},x_{i,a})

同样十分显然。如果x_i!=a,那么x_j=b。如果x_j!=b，那么x_i=a。

3. x_i=a 一定满足

建边(x_{i,a\oplus1},x_{i,a})

考虑该操作的意义。首先可以知道，x_{i,0}和x_{i,1}必须选择且仅选择一个。那么，因为x_i=a一定满足，则x_i!=a的点不可以取。那么，直接建边(x_{i,a\oplus1},x_{i,a})可以控制x_{i,a\oplus1}这个点一定不可选择，否则无解。

可以证明，以上3种情况囊括了所有可能的多元限制。其余限制可以通过转化变成以上3种。

经过操作后，你就得到了一张有向图。开始考虑这张图的作用。

首先，对于这张图中的每个强连通分量中的点一定要么同时选，要么同时不选。

那么，我们将图缩强连通分量。

这时候就可以判断无解了。如果x_{i,0}和x_{i,1}在同一个强连通分量中，那么明显无解。

此时，你就得到了一张拓扑图。这张拓扑图中，如果u可以到达v，那么u选择则v也必须选择。

那么，你可以利用强连通分量的标号来得到反向的拓扑序。

再结合上面的性质，可以得到一个选择策略:

在x_{i,0}和x_{i,1}中选择拓扑序较大的点。

这样就可以避免产生冲突了。并且这种方法一定可以构造出解。

这样2-sat求解就完成了。其瓶颈在强连通分量的处理，利用Tarjan可以做到O(n+m)已抵达输入下界。因此，时间复杂度为O(n+m)。

核心代码:

static int dfn[MAXN<<1],low[MAXN<<1],bel[MAXN<<1];
static int e,cnt,sta[MAXN<<1],tp;

void tarjan(int u)
{
    dfn[u]=low[u]=++e;sta[++tp]=u;
    for(register int v:ed[u])
    {
        if(!dfn[v])tarjan(v),Chkmin(low[u],low[v]);
        else if(!bel[v])Chkmin(low[u],dfn[v]);
    }
    if(low[u]==dfn[u])for(++cnt;sta[tp+1]^u;--tp)
        bel[sta[tp]]=cnt;
}

inline void solve()
{
    Rep(i,2,n<<1|1)if(!dfn[i])tarjan(i);
    Rep(i,1,n)if(bel[i<<1]==bel[i<<1|1])return (void)puts("IMPOSSIBLE");
    puts("POSSIBLE");
    Rep(i,1,n)write(bel[i<<1]>bel[i<<1|1],' ');
}