「JSOI2010」满汉全席 - 2-SAT

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

题意描述

洛谷链接

大会的规则如下：每位参赛的选手可以得到 \(n\) 种材料，选手可以自由选择用满式或是汉式料理将材料当成菜肴。

大会的评审制度是：共有 \(m\) 位评审员分别把关。只要参赛者能在这两种材料的做法中，其中一个符合评审的喜好即可通过该评审的审查。

但大会后来发现，在这样的制度下如果材料选择跟派出的评审员没有特别安排好的话，所有的参赛者最多只能通过部分评审员的审查而不是全部，所以可能会发生没有人通过考核的情形。

所以大会希望有人能写一个程序来判断，所选出的 \(m\) 位评审，会不会发生没有人能通过考核的窘境，以便协会组织合适的评审团。

解题思路

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

把 \(\text{h}x\) 对应为 \(x\) 节点，把 \(\text{m}x\) 对应为 \(n + x\) 节点。对于一组限制 \(x\)，\(y\)，则说明若选了 \(x \pm n\) 则必选 \(y\)，或若选了 \(y \pm n\) 则必选 \(x\)（前者若为汉式则取加号，若为满式则取减号）。然后跑一遍 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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
#include <cstdio>
#include <cctype>
#include <vector>
#include <stack>

const int MAXN = 1000;

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];

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);
    }
}

void prepare(int n) {
    for (int i = 1; i <= 2 * MAXN; i++) {
        N[i].e.clear();
        N[i].dfn = N[i].low = 0;
        N[i].v = false;
        N[i].connected = NULL;
    }
    for (int i = 0; i < 2 * MAXN; i++) {
        connecteds[i].size = connecteds[i].id = 0;
    }
}

int main() {
    int t;

    scanf("%d", &t);

    while (t--) {
        int n, m;
        scanf("%d %d", &n, &m);

        prepare(n);

        while (m--) {
            int i, j;
            char a = ' ', b = ' ';
            while (isspace(a)) a = getchar();
            scanf("%d", &i);
            while (isspace(b)) b = getchar();
            scanf("%d", &j);
            a = a == 'h' ? 1 : 0;
            b = b == 'h' ? 1 : 0;
            if (a && b) {
                addEdge(i + n, j);
                addEdge(j + n, i);
            } else if(!a && b) {
                addEdge(i, j);
                addEdge(j + n, i + n);
            } else if (a && !b) {
                addEdge(i + n, j + n);
                addEdge(j, i);
            } else if (!a && !b) {
                addEdge(i, j + n);
                addEdge(j, i + n);
            }
        }

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

        bool flag = true;
        for (int i = 1; i <= n; i++) {
            if (N[i].connected == N[n + i].connected) {
                flag = false;
                break;
            }
        }

        if (flag) puts("GOOD");
        else puts("BAD");
    }

    return 0;
}