LGP4782 [LG TPLT] 2-SAT 学习笔记
Luogu Link
前言
为什么这个时候才把这个板子过了呢？
……大概是因为以前题解的代码长得太难看了？
……这是借口吗？
题意简述
有 \(n\) 个布尔变量与 \(m\) 个需要满足的条件。每个条件的形式都形如 \(x_i=a_k\lor x_j=b_k\)。其中 \(a_k\) 和 \(b_k\) 取值为 \(0\) 或 \(1\)。
问能否给出使得一组方案满足所有要求。若可以，给出一组方案。
做法解析
图论建模。
\(x_i=a_k\lor x_j=b_k\) 可以写成：“若 \(x_i\) 不满足 \(a_k\) 则 \(x_j\) 必须满足 \(b_k\)，若 \(x_j\) 不满足 \(b_k\) 则 \(x_i\) 必须满足 \(a_k\)”。我们把问题放到图论上，令结点 \(i\) 表示 \(x_i=1\) 的情况，结点 \(i+n\) 表示 \(x_i=0\) 的情况，于是我们就可以连出两条边：\(i_{\neg a_k}\to j_{b_k}\)、\(j_{\neg b_k}\to i_{a_k}\)。然后跑强连通分量。
为什么是强连通分量呢？\(u\to v\) 意味着若 \(u\) 则 \(v\)，也即 \(u\) 与 \(v\) 取值。我们对于每一对 \((i,i+n)\) 都需要“激活”其中的一个点（要么 \(i\) 为真成立，要么 \(i\) 为假成立），激活一个点后它能到达的所有点的真假也会与它一样。你处理完强连通分量之后若 \(x\) 和 \(x+n\) 处于同一强连通分量中即说明无解，因为无论你激活其中的哪个都避免不了另一个被激活。
代码实现
#include <bits/stdc++.h>
using namespace std;
using namespace obasic;
const int MaxN=1e6+5;
int N,M,X,Y,ya,yb,na,nb;
vector<int> Gr[MaxN<<1];
int dfn[MaxN<<1],low[MaxN<<1],stk[MaxN<<1],ktp;
int tot,ccnt,bel[MaxN<<1];
void tarjan(int u){dfn[u]=low[u]=++tot,stk[++ktp]=u;for(auto v : Gr[u]){if(!dfn[v])tarjan(v),minner(low[u],low[v]);else if(!bel[v])minner(low[u],dfn[v]);}if(dfn[u]==low[u]){ccnt++;int v;for(int v;ktp;){v=stk[ktp--],bel[v]=ccnt;if(v==u)break;}}
}
bool twosat(int 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 false;return true;
}
int main(){readis(N,M);for(int i=1;i<=M;i++){readis(X,ya,Y,yb);na=ya^1,nb=yb^1;Gr[X+na*N].push_back(Y+yb*N);Gr[Y+nb*N].push_back(X+ya*N);}if(twosat(N)){puts("POSSIBLE");for(int i=1;i<=N;i++)writip(bel[i]>bel[i+N]);}else puts("IMPOSSIBLE");return 0;
}