DDOSvoid's Blog

2-sat

发表于 更新于 分类于
本文字数： 3.2k 阅读时长 ≈ 3 分钟

简介

问题大概就是多个 $01$ 变量之间存在 $k$ 元限制，要求在满足限制的情况下构造合法方案

首先我们将所有点拆成两个，$i$ 和 $i’$ 分别表示取 $0$ 和取 $1$ 的情况，边 $u\rightarrow v$ 表示如果选 $u$ 就必须选 $v$

一共有三类限制，其中 $a$ 和 $b$ 的取值为 $0/1$

  1. 若 $x_i$ 是 $a$，则 $x_j$ 一定是 $b$，反之也成立，那么需要建两条边直接 $x_{i,a}\rightarrow x_{j,b}$ 和 $x_{j,b~xor~1}\rightarrow x_{i,a~xor~1}$
  2. $x_i$ 是 $a$ 和 $x_j$ 是 $b$ 至少满足一个，那么需要连两条边 $x_{i,a~xor~1}\rightarrow x_{j,b}$ 和 $x_{i,a}\rightarrow x_{j,b~xor~1}$
  3. $x_i$ 一定是 $a$，连边 $x_{i,a~xor~1}\rightarrow x_{i,a}$ 这样可以控制在有解的情况下一定选 $x_{i,a }$

注意到这三种限制可以表示出两个变量三种位运算六种结果的所有情况

1
2
3
4
5
6
7
8
9
10
11
12
13
if (s == "AND") {
    if (w) addedge(x, x + n), addedge(y, y + n); //两个变量都一定是 1，限制 3
    else addedge(x + n, y), addedge(y + n, x); // x 是 0 和 y 是 0 至少满足一个，限制 2
}
if (s == "OR") { 
     if (w) addedge(x, y + n), addedge(y, x + n); // x 是 1 和 y 是 1 至少满足一个，限制 2
     else addedge(x + n, x), addedge(y + n, y); // 两个变量都一定是 0，限制 3
}
if (s == "XOR") { // 若 x 是 1，则 y 一定是 0; 若 x 是 0，则 y 一定是 1
     if (w) addedge(x, y + n), addedge(y, x + n), addedge(x + n, y), addedge(y + n, x); 
     else addedge(x, y), addedge(x + n, y + n), addedge(y, x), addedge(y + n, x + n);
     // 若 x 是 0，则 y 一定是 0; 若 x 是 1，则 y 一定是 1
}

一个简单的构造解的方法就是 $i$ 和 $i’$ 选择拓扑序较大的

贴个板子，注意 $bl$ 表示的是拓扑序的逆序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <cstdio>
#include <stack>
#include <queue>
#include <cstring>
#define maxn 1000010
#define maxm 1000010
#define Maxn 2000010
using namespace std;

int n, m;

struct Edge {
    int to, next;
} e[maxm * 2]; int c1, head[Maxn]; 
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int dfn[Maxn], low[Maxn], c2, bl[Maxn], scc;
bool ins[Maxn]; stack<int> S;
void tarjan(int u) {
    dfn[u] = low[u] = ++c2; ins[u] = 1; S.push(u); 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
        else if (ins[v]) low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) { 
        int t; ++scc;
        do {
            t = S.top(); S.pop();
            bl[t] = scc; ins[t] = 0;
        } while (t != u); 
    } 
}

int main() { memset(head, -1, sizeof head); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; 
    for (int i = 1; i <= m; ++i) {
        int x, a, y, b; cin >> x >> a >> y >> b;
        add_edge(x + (a ^ 1) * n, y + b * n);
        add_edge(y + (b ^ 1) * n, x + a * n); 
    }
    for (int i = 1; i <= 2 * n; ++i) if (!dfn[i]) tarjan(i); 
    for (int i = 1; i <= n; ++i) 
        if (bl[i] == bl[i + n]) return cout << "IMPOSSIBLE" << "\n", 0;
    cout << "POSSIBLE" << "\n";
    for (int i = 1; i <= n; ++i)
        cout << (bl[i] > bl[i + n]) << " "; cout << "\n"; 
    return 0;
}

例题

  1. 简要题意：给定一个 $n$ 个点 $m$ 条边的无向图，求有多少种划分方案可以将这 $n$ 个点划分成两个集合 $S,T$，满足 $|S|,|T|\ge 1$ 且 $S$ 是一个团，$T$ 是一个独立集

    $n\le 5000,m\le \frac{n\times (n-1)}{2}$

    简要题解：我们考虑 $2-sat$，$0$ 表示将划分到 $S$，$1$ 表示划分到 $T$，如果 $(u,v)$ 之间有边，那么我们有 $u\rightarrow v’,v\rightarrow u’$，如果 $(u,v)$ 之间无边，那么我们有 $u’\rightarrow v,v’\rightarrow u$，然后我们利用 $2-sat$ 可以求出一个解

    然后我们考虑如何计数，仔细思考可以发现，解的数量是 $O(n^2)$ 范围，且我们可以利用一个解去推出其他解，具体的做法是我们对于已经求出来的一个解，尝试将一个点从 $S$ 移入 $T$，或者将一个点从 $T$ 移入 $S$，或者交换 $S$ 和 $T$ 的一个点，需要注意如果一开始求出来的解不满足 $S$ 和 $T$ 都非空答案要减 $1$

    时间复杂度 $O(n^2)$

    Luogu P3513 [POI2011] KON-Conspiracy

  2. 简要题意：给定一个 $n$ 个点 $m$ 条边的无向图，现在有已经将这 $n$ 个点分成了 $k$ 个集合，求是否可以在每个集合中恰好选一个关键点，且每条边至少有一个端点是关键点

    $n,m\le 10^6$

    简要题解：我们考虑 $2-sat$，对于原图中的边的建图方法非常简单

    注意到一个部分只能选恰好一个点，那么对于这个部分中的每个点 $u$

    我们要建 $|S|$ 条边，分别是 $u\rightarrow v’,v\in S,v\neq u$

    这样总共需要 $O(n^2)$ 条边，我们考虑搞一个前缀点和一个后缀点，这些点串联起来

    那么只需要 $O(n)$ 条边，另外也可以直接用线段树优化建图，但注意到每个点要连的区间是一样的，所以没有必要使用线段树

    Luogu P6378 [PA2010]Riddle