SAT
指Satisfiability(可满足性问题)
k-SAT
指每个限制有
个条件,而当
时该问题为NP完全的,只能暴力
有
个布尔变量
n ,另有
x_1,x_2,\dots,x_n 个需要满足的条件,每个条件的形式都是「
m 为
x_i true
/false
或x_j
为true
/false
」.比如「
为
x_1 true
或为
x_3 false
」、「为
x_7 false
或为
x_2 false
」。
2-SAT
问题的目标是给每个变量赋值使得所有条件得到满足。
查看原题
点击跳转
至少有一个端点是关键点
条件 | 连边 |
---|---|
任选一个 |
|
接下来是对每部分进行连边
若将每个点向该部分中出它以外的所有点连边,复杂度为
我们可以前缀优化建图
设该部分为
对每个点
新增一个状态
表示
中有没有被选为关键点
条件 | 连边 |
---|---|
必须同时选 |
|
必须同时选 |
|
不能同时选 |
|
这样就可以
连边了