现有一个由 N 个布尔值组成的序列 A ,给出一些限制关系,比如 A[x] AND A[y]=0、A[x] OR A[y] OR A[z]=1等,要确定A[0⋯N−1]的值,使得其满足所有限制关系。这个称为SAT问题(已确定非2-SAT的SAT问题为NP完全问题),特别的,若每种限制关系中最多只对两个元素进行限制,则称为 2-SAT 问题。
算法我们可以把每个点拆成两个点,一个代表取值为 true ,另一个代表取值为 false ,对点对进行遍历,如果两个点都没被选,则先假设选 false ,沿边 DFS 对其所有能到达的点都标记为选择,如果染色过程中发现一个点对的两个点都被选了,也就是某个值是 false 会得出这个值为 true,那么就说明假设矛盾,沿路清空标记,然后尝试选 true 进行 DFS,如果再次失败就说明不存在满足所有条件的解。所有点对都有一个点被选了之后,我们就得到了一种整体的选择方式满足所有题目条件。
注意:这里的true和false不是绝对的,要视实际情况而定!比如:妻子(true)&丈夫(false),工作&休假,尽量是对立的!
算法实例接下来,用一个例子说明算法执行的过程。
我们有 3 个布尔值组成的序列 A ,限制条件为:
A[0] OR A[1]=1A[1] AND A[2]=1
首先我们进行拆点,然后连边,根据第一个限制条件,我们把 A[0] 的 false 和 A[1] 的 true 连起来,把 A[1]的 false 和 A[0]的 true 也连起来,连有向边,因为这两个中只要有一个不是 11,另外一个就必须选 1。根据第二个条件,把 A[1] 的 false 和 A[1] 的 true 连有向边,把 A[2] 的 false 和 A[2] 的 true连有向边,因为只要有一个不是 1,这个等式就不可能成立。那么图会变成这样。
我们从 0 开始,发现 0 的 true 和 false 都没有选,那么先尝试选 false。
从这个点开始沿路进行选择,将 1 选为 true。
这时从 0 的 false 出发的路都选完了。再看 1,1 已经选了 true 就不再搜索这个点对了。再看 2 ,尝试选 false 后,自己的 true 也会被选,说明 2 选 false 不行,那么尝试选 true,发现可以,选择完成。
此时所有点对都有一个被选了,选择成功,我们就得到了一组满足所有限制条件的解。
时间复杂度为 O(VE),空间复杂度为 S(V+E)。
C++ 示例代码#include#include using namespace std; const int MAX_N = 100; // 点的上限 const int MAX_M = 10000; // 边的上限 struct edge { int v, next; } E[MAX_M]; int p[MAX_N * 2], eid; void init() { memset(p, -1, sizeof(p)); eid = 0; } void insert(int u, int v) { e[eid].v = v; e[eid].next = p[u]; p[u] = eid++; } int n, m; // n 表示点数, m 表示边数 bool selected[MAX_N * 2]; // 标记每个点对是否被选,每一点对为2*i和2*i+1 int S[MAX_N * 2]; // 标记此次选择经过的点 int c; // 此次选择的点数 bool dfs(int u) { if (selected[u ^ 1]) { return false;//和假设矛盾 } if (selected[u]) { return true;//和假设一样 } selected[u] = true; S[c++] = u; for (int i = p[u]; i != -1; i = E[i].next) { int v = E[i].v; if (!dfs(v)) { return false; } } return true; } bool Two_SAT(int n) { for(int i = 0; i < 2 * n; i += 2) { if (!selected[i] && !selected[i + 1]) { c = 0; if (!dfs(i)) { while (c > 0) { selected[S[--c]] = false; // 失败后沿路清空选择 } if (!dfs(i + 1)) { return false; } } } } return true; } int main() { init(); memset(selected,false,sizeof(selected)); cin>>N>>M; for (int i=0;i >k>>x>>y; if (k==0){ insert(2*x,2*x+1); insert(2*y,2*y+1); }else{ insert(2*x,2*y+1); insert(2*y,2*x+1); } } if (Two_SAT(N)){ cout<<"YES"< 欢迎分享,转载请注明来源:内存溢出
评论列表(0条)