学习笔记

2-SAT学习笔记

概念

SAT,即为适定性(Satisfiability)问题。通俗来讲就是给定 $\text{n}$ 个元素,每个元素都有 $\text{k}$ 种取值。然后给定 $\text{m}$ 条限制条件,问是否有满足所有限制条件的取值方案,若有则给出一组可行的方案。若每个元素最多 $\text{k}$ 种取值,则称之为 K-SAT 问题。
同理,每个元素若有2种取值,则称之为2-SAT问题。取值更多的方案已经被证明为 $\text{NPC}$ 问题,只能暴力做,时间复杂度是指数级的。
2-SAT 问题中的限制都是形如 $x_i\ \text{xor}\ x_j = 1$,$x_i\ \text{and}\ x_j = 1$ 这种形式的。

解法

解法主要有两种,搜索与强连通分量,两种做法都有无可替代的地方。
搜索可以求出字典序最小的解,但是相应的时间复杂度较高;
而强连通分量的时间复杂度是现行的,并且可以求出一组可行解,但是是随机的,不能保证是字典序最小的解。
搜索的话,从没有确定的取值出发,如果这个取值不行就试试另一个,如果都不行就说明无解。
强连通分量只要判断所有变量的两个取值是不是都在一个强连通分量里,如果在就无解。
两种做法的建图都是一样的,而且2-SAT问题也主要考察建图。
先来做一些规定。
首先一个变量只有两种取值,且只能取一种,那么我们就可以把这个变量拆成两个,下面规定点 $i$ 表示 $x_i$ 的取值为 $true$,$i+n$ 表示取值为 $false$。
那么边的含义就是:如果某个变量取某个值,那么另外另一个变量的值必须是什么。
那么有向边$(p_i,p_j)$的含义就是说若 $x_i$ 的取值为 $true$,那么 $x_j$ 的取值也必须是 $true$,同理类比 $false$ 的情况。
规定一下 $i$ 的反变量为 $i’$,就是说 $i\ \text{xor}\ i’ = 1$
回顾一下我做过的题目,根据以下几种限制,可以分别用以下的方法建图。

限制 方法
$a\ \text{xor}\ b = 0$ $(a,b),(a’,b’),(b,a),(b’,a’)$
$a\ \text{xor}\ b = 1$ $(a,b’),(a’,b),(b,a’),(b’,a)$
$a\ \text{and}\ b = 0$ $(a,b’),(b,a’)$
$a\ \text{and}\ b = 1$ $(a’,a),(b’,b)$
$a\ \text{or}\ b = 0$ $(a,a’),(b,b’)$
$a\ \text{or}\ b = 1$ $(a’,b),(b’,a)$
$a = 0$ $(a,a’)$
$a = 1$ $(a’,a)$

综合一下定义的话,上面的内容还是比较显然的。
另外还有一种把所有操作都转化成或的建图方法,
以下内容参考了 Sengxian’s Blog
如果限制都是 $x_i$ 为$true/false$ 或 $x_j$ 为 $true/false$ 的话,可以采用这个函数方便地建图。
$a,b$ 为限制的变量,$va,vb$为这两个变量的限制的取值。

void addClause(int a, int va, int b, int vb) {
    add(a + n * va, b + n * (!vb));
    add(b + n * vb, a + n * (!va));
}

下表摘取自Sengxian’s Blog

条件 对应的语句
a = b (a与b相等) addClause(a, 1, b, 0); addClause(a, 0, b, 1);
a ≠ b (a与b不相等) addClause(a, 0, b, 0); addClause(a, 1, b, 1);
a = b = true (a与b均为true) addClause(a, 1, b, 1); addClause(a, 1, b, 0); add_clause(a, 0, b, 1);
a = b = false(a与b均为false) addClause(a, 0, b, 0); addClause(a, 1, b, 0); add_clause(a, 0, b, 1)

这个表格我个人觉得更直观一点,有兴趣的读者可以研究一下,说白了就是要求变量之间按照定义必须满足什么条件,组合一下就是前面的条件。

核心代码

搜索

搜索的代码我没写过几遍,这份也是临时yy的,慎抄,Sengxian的博客里的更靠谱一点。

bool dfs(int u) {
    if (u > n && mark[u - n]) return false;
    else if (mark[u + n]) return false;
    if (mark[u]) return true;
    mark[u] = true;
    stack.push(u);
    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        if (!dfs(v)) return false;
    }
    return true;
}
bool solve() {
    for (int i = 1; i <= n; i++) {
        if (!dfs(i)) {
            while (!stack.empty()) mark[stack.top()] = false, stack.pop();
            if (!dfs(i + n)) return false;
        }
    }
    return true;
}

SCC

void Tarjan(int u) {
    dfn[u] = low[u] = ++ts;
    inStack[u] = true;
    stack.push(u);
    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        if (!dfn[v]) Tarjan(v), low[u] = std::min(low[u], low[v]);
        else if (inStack[v]) low[u] = std::min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        ++tot;
        do {
            mark[u] = tot;
            u = stack.top(); stack.pop();
            inStack[u] = false;
        } while (low[u] != dfn[u]);
    }
}
bool solve() {
    for (int i = 1; i <= 2 * n; i++) {
        if (!dfn[i]) Tarjan(i);
    }
    for (int i = 1; i <= n; i++) {
        if (mark[i] == mark[i + n]) {
            return false;
        }
    }
    return true;
}

输出方案

搜索的输出方案非常简单,$dfs$的时候已经求出来了。
强连通分量的话,只需要对于每个变量都取拓扑序大的那个就可以了。
这里其实不用再写一份拓扑排序,因为求出强连通分量的顺序是反拓扑序(先给栈顶标号,而最后入栈的强连通分量是出度为0的,与拓扑排序正好相反),输出的时候判断一下就可以了,注意是反拓扑序,别标错符号。

模板题

Luogu4782

代码

#include <cstdio>
#include <climits>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <stack>
const int MAXN = 1e6 + 7;
struct Edge {
    int t, next;
} edge[MAXN << 1];
int n, m;
int head[MAXN << 1], cnt;
int mark[MAXN << 1], tot;
int dfn[MAXN << 1], low[MAXN << 1], ts;
bool inStack[MAXN << 1];
std::stack<int> stack;
void add(int u, int v) {
    edge[++cnt] = (Edge){v, head[u]}; head[u] = cnt;
}
void addClause(int a, int va, int b, int vb) {
    add(a + n * va, b + n * (!vb));
    add(b + n * vb, a + n * (!va));
}
void Tarjan(int u) {
    dfn[u] = low[u] = ++ts;
    inStack[u] = true;
    stack.push(u);
    for (int e = head[u]; e; e = edge[e].next) {
        int v = edge[e].t;
        if (!dfn[v]) Tarjan(v), low[u] = std::min(low[u], low[v]);
        else if (inStack[v]) low[u] = std::min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        ++tot;
        do {
            mark[u] = tot;
            u = stack.top(); stack.pop();
            inStack[u] = false;
        } while (low[u] != dfn[u]);
    }
}
int main(int argc, char *argv[]) {
    scanf("%d %d", &n, &m);
    int u, v, uv, vv;
    for (int i = 1; i <= m; i++) {
        scanf("%d %d %d %d", &u, &uv, &v, &vv);
        addClause(u, uv, v, vv);
    }
    for (int i = 1; i <= 2 * n; i++) {
        if (!dfn[i]) Tarjan(i);
    }
    for (int i = 1; i <= n; i++) {
        if (mark[i] == mark[i + n]) {
            puts("IMPOSSIBLE");
            return 0;
        }
    }
    puts("POSSIBLE");
    for (int i = 1; i <= n; i++) {
        printf("%d ", mark[i] < mark[i + n]);
    }
    puts("");
    return 0;
}

参考资料

【算法学习】2-SAT
【研究总结】2-sat问题
2-sat

发表评论

电子邮件地址不会被公开。 必填项已用*标注