「洛谷 P5782」和平委员会 - 2-SAT

发表于 分类于 ， 阅读次数： Disqus：

题意描述

洛谷链接

根据宪法，Byteland 民主共和国的公众和平委员会应该在国会中通过立法程序来创立。 不幸的是，由于某些党派代表之间的不和睦而使得这件事存在障碍。 此委员会必须满足下列条件：

  • 每个党派都在委员会中恰有 \(1\) 个代表。
  • 如果 \(2\) 个代表彼此厌恶，则他们不能都属于委员会。

每个党在议会中有 \(2\) 个代表。代表从 \(1\) 编号到 \(2n\)。 编号为 \(2i-1\) 和 \(2i\) 的代表属于第 \(i\) 个党派。

任务：写一程序读入党派的数量和关系不友好的代表对，计算决定建立和平委员会是否可能，若行，则列出委员会的成员表。

对于 \(100\%\) 的数据，\(1 \leq n \leq 8000\)，\(0 \leq m \leq 20000\)，\(1 \leq a < b \leq 8000\)。

解题思路

显然这是一道 2-SAT 问题。

如果 \(a\) 与 \(b\) 互相厌恶，那么只能 \(a\) 出现时 \(b \oplus 1\) 必定出现，或 \(b\) 出现时 \(a \oplus 1\) 必定出现。连接 \(a \rightarrow (b \oplus 1)\) 和 \(b \rightarrow (a \oplus 1)\) 这两条边，然后跑一遍 2-SAT 就得出答案了。

代码演示

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <cstdio>
#include <vector>
#include <stack>

const int MAXN = 80000;

struct Node {
    std::vector<struct Edge> e;
    int dfn, low;
    bool v;
    struct Connected *connected;
} N[2 * MAXN + 1];

struct Edge {
    Node *s, *t;

    Edge(Node *s, Node *t) : s(s), t(t) {}
};

struct Connected {
    int size, id;
} connecteds[2 * MAXN + 1];

inline void addEdge(int s, int t) {
    N[s].e.push_back(Edge(&N[s], &N[t]));
}

void tarjan(Node *x) {
    static int num = 0, counts = 0;
    static std::stack<Node *> stk;
    x->dfn = x->low = ++num;
    stk.push(x);
    x->v = true;

    for (Edge *e = &x->e.front(); e && e <= &x->e.back(); e++) {
        if (!e->t->dfn) {
            tarjan(e->t);
            x->low = std::min(x->low, e->t->low);
        } else if (e->t->v) {
            x->low = std::min(x->low, e->t->dfn);
        }
    }

    if (x->dfn == x->low) {
        counts++;
        connecteds[counts].id = counts;
        Node *y;
        do {
            y = stk.top();
            stk.pop();
            y->v = false;
            y->connected = &connecteds[counts];
            connecteds[counts].size++;
        } while (x != y);
    }
}

int main() {
    int n, m;

    scanf("%d %d", &n, &m);

    while (m--) {
        int a, b;
        scanf("%d %d", &a, &b);
        addEdge(a, b % 2 ? b + 1 : b - 1);
        addEdge(b, a % 2 ? a + 1 : a - 1);
    }

    for (int i = 1; i <= 2 * n; i++) {
        if (!N[i].dfn) {
            tarjan(&N[i]);
        }
    }

    for (int i = 1; i <= 2 * n; i += 2) {
        if (N[i].connected == N[i + 1].connected) {
            puts("NIE");
            return 0;
        }
    }

    for (int i = 1; i <= 2 * n; i += 2) {
        printf("%d\n", N[i].connected->id < N[i + 1].connected->id ? i : i + 1);
    }

    return 0;
}