[JSOI 2010] 满汉全席

发表于2017-04-11更新于2020-08-06

题目大意

给定 nn 种材料，对于每种材料，有满式、汉式两种做法（一种材料只能选择一种做法）。有 mm 个评委，每个评委有两道要求的菜（菜由一种材料加一种做法构成），这两道菜至少要做出一道才能让评委满意。现询问是否能让所有评委满意，能输出 GOOD，不能输出 BAD。多组询问。

1⩽T⩽501 \leqslant T \leqslant 50

1⩽n⩽1001 \leqslant n \leqslant 100

1⩽m⩽1,0001 \leqslant m \leqslant 1,000

题目链接

【JSOI 2010】满汉全席 - Luogu 4171

题解

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
#include <cstdio>
#include <stack>
#include <algorithm>
// #define DBG
const int MAXN = 105;
const int MAXM = 1005;
struct Edge;
struct Node {
    Edge *e;
    int dfn, low, belong;
    bool inq;
} N[MAXN << 1];
struct Edge {
    Node *u, *v;
    Edge *next;
    Edge(Node *u, Node *v) : u(u), v(v), next(u->e) {}
};
void addEdge(int u, int v) {
#ifdef DBG
    printf("edge : %d --> %d\n", u, v);
#endif
    N[u].e = new Edge(&N[u], &N[v]);
}
void clearGraph(int n) {
    for (int i = 1; i <= n; i++) {
        for (Edge *&e = N[i].e, *next; e; next = e->next, delete e, e = next);
        N[i].low = N[i].dfn = N[i].belong = 0;
        N[i].inq = false;
    }
}
int getV(int x, int k) {
    return (x << 1) - k;
}
struct twoSat {
    std::stack<Node *> s;
    int dfsClock, sccCnt;
    void tarjan(Node *u) {
        s.push(u);
        u->inq = true;
        u->dfn = u->low = ++dfsClock;
        for (Edge *e = u->e; e; e = e->next) {
            if (e->v->dfn == 0) {
                tarjan(e->v);
                u->low = std::min(u->low, e->v->low);
            } else if (e->v->inq) u->low = std::min(u->low, e->v->dfn);
        }
        if (u->dfn == u->low) {
            Node *c;
            sccCnt++;
            while (true) {
                c = s.top();
                s.pop();
                c->belong = sccCnt;
                c->inq = false;
                if (c == u) break;
            }
        }
    }
    bool check(int n) {
        for (int i = 1; i <= n; i++) 
            if (N[getV(i, 0)].belong == N[getV(i, 1)].belong) return false;
        return true;
    }
    bool operator()(int n) {
        dfsClock = sccCnt = 0;
        while (!s.empty()) s.pop();
        for (int i = 1; i <= n << 1; i++) if (N[i].dfn == 0) tarjan(&N[i]);
#ifdef DBG
        printf("sccCnt = %d\n", sccCnt);
#endif
        return check(n);
    }
} ts;
int parseInt(char *s) {
    int res = 0;
    for (char *p = s; *p; p++) res = res * 10 + *p - '0';
    return res;
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        int n, m;
        scanf("%d %d", &n, &m);
        clearGraph(n << 1);
        for (int i = 1; i <= m; i++) {
            char kx[5], ky[5];
            int x, y, xv, yv;
            scanf("%s", kx);
            x = parseInt(kx + 1);
            scanf("%s", ky);
            y = parseInt(ky + 1);
            xv = kx[0] == 'm';
            yv = ky[0] == 'm';
            addEdge(getV(x, xv ^ 1), getV(y, yv));
            addEdge(getV(y, yv ^ 1), getV(x, xv));
        }
        puts(ts(n) ? "GOOD" : "BAD");
    }
    return 0;
}