[BZOJ 1823][JSOI 2010] 满汉全席

题目大意

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

\(1 \leqslant T \leqslant 50\)

\(1 \leqslant n \leqslant 100\)

\(1 \leqslant m \leqslant 1,000\)

题目链接

BZOJ 1823

题解

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