前言
由于蒟蒻才刚开始学 ( ext{2-SAT})，所以题解中有的地方可能不够精炼，望多包涵！
题目描述
题目意思很简单，标准的( ext{2-SAT})问题模型。那么我们就先来介绍一下 ( ext{2-SAT}) （以下是个人的小小概括）
( ext{2-SAT}) 问题，抽象化一下，是这样的：
给出 (n) 个布尔变量 ({x_n})，以及 (m) 个命题 ((a,aa,b,bb))，一个命题成立的条件是([x_a=aa]lor[x_b=bb])
现在就是要判断是否一种方案，将({x_n})中的每个元素赋一个值，使所有的(m)个命题成立
对于这种问题，我们用一下方法来建立图的模型：
对于 (n) 个不同变量 (x)，我们将其拆成两个点，分别表示 (x) 为真和 (x) 为假（可以用 (i) 表示 (x_i) 为真，(i+n) 表示 (x_i) 为假）
接下来对于每一条有向边 ((a,b))，我们赋予它这样的意义：若 (a) 应该被满足，则 (b) 也必须被满足
这样一来，我们就可以用如下的方法判定有无解：
- 有解的情况：(forall iin n), (i) 和 (i+n) 不属于同一个强连通分量。
- 无解的情况：(exists iin n), (i) 和 (i+n) 属于同一个强连通分量。
因为按照我们上面的建边方法，属于同一个强连通分量的两个点他们所代表的命题是要同时为真的。
而因为同一个布尔变量 (x) 不会同时有两种值，所以以上判断方法的正确性是显然的。
那么我们就只需建好图，跑一遍 ( ext{Tarjan}) 再按照上述方法判断即可。
那么，接下来就是最重要的一步：如何建图？
其实这并不难，只要能抽象出 ({x_n}) 和 (m) 个命题就好，以这道题为例，加深一下理解。
基本思路
我们把(n)样食材抽象成({x_n})，第 (i) 样食材做成汉式表示 (x_i) 为真（点 (i)），反之表示 (x_i) 为假（点 (i+n)）
然后对于每一位评审的需求，也类似地按照上面的方法抽象一下
然后对于每一项需求给出的两个命题 (p,q)，我们连两条边 ((lnot p,q)) 和 ((lnot q, p))
（至于这里的 (p) 和 (q)是什么，可以自己思考一下）
细节注意事项
- 由于我们的 (n) 样食材会被拆成两个点，所以点的空间要开两倍。
- 由于我们的 (m) 项需求会产生两条边，所以边的空间也要开两倍。
- 每一次初始化时，如果用( ext{for})循环清空数组，千万要注意枚举的上界（见上两条）。
参考代码
可能我写的不是很好，没有看明白的话可以结合我的代码理解给个好评吧啊啊啊
/*--------------------------------
Code name: meal.cpp
Author: The Ace Bee
This code is made by The Ace Bee
--------------------------------*/
#include <cstdio>
#include <cstring>
#define rg register
#define fileopen(x)
freopen(x".in", "r", stdin);
freopen(x".out", "w", stdout);
#define fileclose
fclose(stdin);
fclose(stdout);
const int MAXN = 233;
const int MAXM = 2333;
inline int min(int a, int b) { return a < b ? a : b; }
inline int read() {
int s = 0; bool f = false; char c = getchar();
while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
while (c >= '0' && c <= '9') s = (s << 3) + (s << 1) + (c ^ 48), c = getchar();
return f ? -s : s;
}
int tot, head[MAXN], nxt[MAXM], ver[MAXM];
inline void Add_edge(int u, int v)
{ nxt[++tot] = head[u], head[u] = tot, ver[tot] = v; }
int n, num, dfn[MAXN], low[MAXN];
int st[MAXN], top, co[MAXN], col;
inline void tarjan(int u) {
dfn[u] = low[u] = ++num, st[++top] = u;
for (rg int v, i = head[u]; i; i = nxt[i]) {
if (!dfn[v = ver[i]])
tarjan(v), low[u] = min(low[u], low[v]);
else
if (!co[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
++col;
do co[st[top]] = col, --top;
while (st[top + 1] != u);
}
}
inline void init() {
tot = col = num = top = 0;
memset(co, 0, sizeof co);
memset(dfn, 0, sizeof dfn);
memset(low, 0, sizeof low);
memset(head, 0, sizeof head);
}
int main() {
// fileopen("meal");
char sa[10], sb[10];
for (rg int T = read(); T; --T) {
init();
int n = read();
for (rg int m = read(); m; --m) {
scanf("%s%s", sa, sb);
int a = 0, lena = strlen(sa);
for (rg int i = 1; i < lena; ++i)
a = (a << 3) + (a << 1) + (sa[i] ^ 48);
int b = 0, lenb = strlen(sb);
for (rg int i = 1; i < lenb; ++i)
b = (b << 3) + (b << 1) + (sb[i] ^ 48);
if (sa[0] == 'h' && sb[0] == 'h')
Add_edge(a + n, b), Add_edge(b + n, a);
else if (sa[0] == 'h' && sb[0] == 'm')
Add_edge(a + n, b + n), Add_edge(b, a);
else if (sa[0] == 'm' && sb[0] == 'h')
Add_edge(a, b), Add_edge(b + n, a + n);
else if (sa[0] == 'm' && sb[0] == 'm')
Add_edge(a, b + n), Add_edge(b, a + n);
}
for (rg int i = 1; i <= n << 1; ++i)
if (!dfn[i]) tarjan(i);
int flag = 1;
for (rg int i = 1; i <= n; ++i)
if (co[i] == co[i + n]) { flag = 0; break; }
puts(flag ? "GOOD" : "BAD");
}
// fileclose;
return 0;
}
完结撒花 (qwq)