「OI」2-SAT

$\texttt{SAT}$ 是适定性(Satisfiability)问题的简称。一般形式为 $\texttt{k}$ – 适定性问题,简称 $\texttt{k-SAT}$。而当 $\texttt{k}>2$ 时该问题为 NP 完全的。所以我们只研究 $\texttt{k}=2$ 的情况。

$\texttt{2-SAT}$

定义

$\texttt{2-SAT}$,简单的说就是给出 $n$ 个集合,每个集合有两个元素 $a,b$,已知若干个 $<a,b>$,表示 $a$ 与 $b$ 矛盾(其中 $a$ 与 $b$ 属于不同的集合)。然后从每个集合选择一个元素,判断能否一共选 $n$ 个两两不矛盾的元素。显然可能有多种选择方案,一般题中只需要求出一种即可。

2-SAT-Z0.png

基本思路

其实这个比较简单,就是基本的简单逻辑,如果由 $a$ 可以推出 $b$,那么建一条边 $a\to b$。

判断是否有解比较简单,判断集合内两个点是不是在同一个强连通分量内,用 $\texttt{Tarjan}$ 即可。

输出一个解也比较简单,根据拓扑序可以得出结果,不过 $\texttt{Tarjan}$ 的拓扑序是反的,需要注意。

简单技巧

其实就是数学的逻辑。

$$
a\to b\Leftrightarrow
\begin{cases}
a&\to b\\
\lnot b&\to \lnot a
\end{cases}
$$

$$
a\lor b\Leftrightarrow
\begin{cases}
\lnot a\to b\\
\lnot b\to a
\end{cases}
$$

$$
a\oplus b\Leftrightarrow
\begin{cases}
a\to\lnot b\\
b\to\lnot a\\
\lnot a\to b\\
\lnot b\to a
\end{cases}
$$

推荐题目