Creator's World

一、简介

简单来说，就是有 $n$ 个布尔变量 $x_i$，有 $m$ 个条件，每个条件都形如“$x_i$ 为真 $/$ 假或者 $x_j$ 为真 $/$ 假”（“或者”指至少满足其中一个条件）。问是否有一种 $x_i$ 的取值满足上面所有条件。

二、解法

将每个布尔变量看作两个点，然后根据条件建边。对于每一个条件“$x_i$ 为真 $/$ 假或者 $x_j$ 为真 $/$ 假“，点 $x_i$ 表示 $x_i$ 取真，点 $x_i'$ 表示 $x_i$ 取假，$x_j$ 同理。若有条件 $x_i$ 为真或者 $x_j$ 为假“，则连一条 $x_i'$ 向 $x_j'$，表示若 $x_i$ 取假则 $x_j$ 一定要取假（因为 $x_i$ 取假的话只有 $x_j$ 取假才能满足该条件），同理连 $x_j$ 向 $x_i$ 的边。

显然在一个环中若选了一个点，则整个环都要选，因此我们考虑 tarjan 缩点。至于判断是否存在方案，我们发现若 $x_i$ 和 $x'_i$ 在同一个强连通分量中，则不存在，否则的话存在。

然后是输出方案的问题。因为 $u\rightarrow v$ 表示选了 $u$ 一定选 $v$，而缩点后图是 DAG，满足拓扑序。因此对于每一个 $x_i$ 判断它的两个点 $x_i$ 和 $x_i'$ 谁的拓扑序更大就选谁，另外一个直接舍去。而 tarjan 后的强连通分量编号和拓扑序相反，选编号小的点。

三、例题

P4782 【模板】2-SAT 问题

模板题。

P4171 [JSOI2010] 满汉全席

模板题。不过注意字符串读入，编号可能不止一位！

UVA1146 Now or later

看到求满足条件的最小值就想到二分，但如何判断时间是否合法呢？因为每架飞机有两种可能，因此想到 2-SAT，枚举若相隔时间小于最小值，则连另一个的边。

P3825 [NOI2017] 游戏

发现每个场最多放两种车，直接 2-SAT，不过有些细节比较麻烦。