2-SAT 小技巧

· · 算法·理论

2-SAT 表示 k 个点至多选一个

点数 边数
前缀和 2k 6k-4
二进制 2\lceil\log_2 k\rceil 2k \lceil\log_2 k\rceil
神秘做法 2m km

（最小 m 使得 \binom{2m}{m}\ge k）

2-SAT

有一个数组 a，每个数 a_i 可选 0 或 1，拆为两个点 a_{i,0} 和 a_{i,1}。

一些定义

$\text{EDGE}(i, j, x_1, x_2)$ 表示连边： - $a_{i,x1}\to a_{j,x2}$。 $\text{NAND}(i, j, x_1, x_2)$ 表示： - $\text{EDGE}(i, j, x_1, \neg x_2)$。 - $\text{EDGE}(j, i, x_2, \neg x_1)$。 ### 问题 考虑一个这样的限制条件：有 $k$ 对 $(x_i,t_i)$（$t_i\in[0, 1]$），用尽量少的额外点和边表示「至多有一个 $a_{x_i}=t_i$」的限制。 ### 前缀和 新建 $k$ 个数 $a_{y_{1\sim k}}$，$a_{y_i}$ 表示考虑 $x_{1\sim i}$ 时的限制。 对于 $i\in[1,n]$： - $\text{NAND}(x_i,y_i,t_i,0)$。 对于 $i\in(1,n]$： - $\text{NAND}(y_{i-1},y_i,1,0)$。 - $\text{NAND}(y_{i-1},x_i,1,t_i)$。 ### 二进制 新建 $m=\lceil\log_2k\rceil$ 个数 $a_{y_{1\sim m}}$，$a_{y_i}$ 表示考虑二进制下第 $i$ 位时的限制。 对于 $i\in[1,n],j\in[1,m]$，$s_{i,j}$ 表示 $i$ 二进制下从右往左数第 $j$ 位是否为 $t_i$： - $\text{NAND}(x_i,y_j,s_{i,j},\neg s_{i,j})$。