Description
今天 div2 又开会了，但 F_know 又又睡过头了，于是问 neko 会上讲了啥。
neko 说今天总共讲了 $n$ 件事，每件事都有一个重要度，第 $i$ 件事的重要度为一个整数 $a_i$ 。与上次不同的是，$a_i$ 只有两个值 $0$ 或 $1$，分别代表这件事不重要或重要。
neko 记不清 $a_i$ 具体为多少了，他只记得 $m$ 个约束条件，第 $j$ 个约束条件有四个整数 $u,x,v,y$，表示 $a_u=x$ 与 $a_v=y$ 两者至少有一个成立。
请判断是否至少存在一组 $a$ 的值满足上述条件。
2-SAT问题
有$N$个变量，每个变量只有两种可能的取值。再给定$M$个条件，每个条件都是对两个变量的取值限制。求是否存在对$N$个变量的合法赋值，使得$M$个条件均满足。这个问题被称为$\text{2-SAT}$问题。$\text{SAT}$是英文$satisfiability$的缩写，意为可满足性。
Solution
设一个变量 $A_i(1 \le i \le n)$ 的两种可能取值分别是 $A_{i,0}$ 和 $A_{i,1}$ 。在 $\text{2-SAT}$ 问题中，$M$ 个条件都可以转化为统一的形式——”若变量 $A_i$ 赋值为 $A_{i, p}$ ，则变量 $A_j$ 必须赋值为 $A_{j,q}$ “，其中 $p, q \in \lbrace 0, 1 \rbrace$
$\text{2-SAT}$ 问题判定方法如下：
- 建立$2N$个节点的有向图，每个节点 $A_i$ 对应两个节点，一般设为 $i$ 和 $i + N$ ，分别表示 $A_i = A_{i,0}$ 和 $A_i = A_{i,1}$
- 考虑每个条件，形如”若变量 $A_i$ 赋值为 $A_{i, p}$ ，则变量 $A_j$ 必须赋值为 $A_{j,q}$ “， $p, q \in \lbrace 0, 1\rbrace$ 。从 $i + p \times N$ 到 $j + q \times N$ 连接一条有向边
- 用 $\text{Tarjan}$ 算法求出有向图中的所有强联通分量
- 若 $\exists i \in [1, N]$ 使得 $i $ 和 $i+N$ 属于同一个强联通分量，则表明：若变量 $A_i$ 赋值为 $A_{i,p}$，则变量 $A_i$ 必须赋值为 $A_{i,1-p}$ $(\forall p \in [0, 1])$。 这显然是矛盾的，说明是无解。若不存在这样的 $i$，则问题一定有解。
时间复杂度$\mathcal O(N +M)$
回到本题，$a_u = x$ 和 $a_v = y$ 两者至少有一个成立，即
$$
a_u = x \lor a_v = y \\
\Rightarrow
\begin{cases}
a_u \ne x \Longrightarrow a_v = y \\
a_v \ne y \Longrightarrow a_u = x
\end{cases}
$$
例如题目样例，按照上述方法连边（为了更直观，我把点的编号换成了点的实际含义）：
从图中不难看出原题是有解的，且有两组解，分别为$(a_1, a_2, a_3) = (0, 0, 1)$ 和 $(a_1, a_2, a_3) = (1, 1, 0)$ , 实际上对于有解的情况，我们可以通过拓扑顺序构造出一组合法解，即对每个变量 $A_i$ 赋值为结点 $A_{i,0}$ 和 $A_{i,1}$ 中拓扑序靠后的点代表的取值，这样可以避免出现矛盾。
Code
// ID: LRL52 Date: 2022.4.9
#define rep(i, a, b) for(int i = (a); i <= (b); ++i)
#define ee(i, a) for(int i = head[a]; i; i = e[i].nxt)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 55, M = 1e6 + 55; char ss[1 << 21], * A = ss, * B = ss, cc;
inline char gc() { return A == B && (B = (A = ss) + fread(ss, 1, 1 << 21, stdin), A == B) ? EOF : *A++; }
template<class T>inline void rd(T& x) {
int f = 1; x = 0; cc = gc(); while (cc < '0' || cc > '9') { if (cc == '-') f = -1; cc = gc(); }
while (cc >= '0' && cc <= '9') { x = x * 10 + (cc ^ 48); cc = gc(); } x *= f;
}
struct Edge {
int v, nxt;
}e[M << 1];
int dfn[N << 1], low[N << 1], n, m, scc[N << 1];
int clk, top, head[N << 1], ct, stk[N << 1], co;
template<typename T>inline T cmin(T& x, T y) { return y < x ? x = y : x; }
inline void adde(int from, int to) {
e[++ct].v = to;
e[ct].nxt = head[from];
head[from] = ct;
}
void tarjan(int x) {
low[x] = dfn[x] = ++clk; stk[top++] = x;
ee(i, x) {
int v = e[i].v;
if (!dfn[v]) {
tarjan(v);
cmin(low[x], low[v]);
}
else if (!scc[v]) cmin(low[x], dfn[v]);
}
if (low[x] == dfn[x]) {
++co;
do {
int v = stk[--top];
scc[v] = co;
} while (stk[top] != x);
}
}
int main()
{
//freopen("I.in", "r", stdin);
rd(n), rd(m); int x, y, a, b;
rep(i, 1, m) {
rd(x), rd(a), rd(y), rd(b);
adde(x + n * (a & 1), y + n * (b ^ 1));
adde(y + n * (b & 1), x + n * (a ^ 1));
}
rep(i, 1, n << 1) if (!dfn[i]) tarjan(i);
rep(i, 1, n) {
if (scc[i] == scc[i + n]) {
puts("NO");
return 0;
}
}
puts("YES");
//rep(i, 1, n) printf("%d ", scc[i + n] > scc[i]);
return 0;
}
Reference
- 《算法竞赛进阶指南》李煜东 著
- 洛谷 P4782 【模板】2-SAT 问题
题解同步发表在Blog
