前置知识：2-SAT
题目大意
有 n 种材料，每种可做满式（m）或汉式（h）。m 位评审各有两个喜好（如 m1、h2），只要选手做出其中一个喜好的菜，该评审就通过。
问：是否存在一种做菜方案，能让所有评审都通过？
存在输出
GOOD，否则输出BAD。
解题思路
显然这是一道2-SAT裸题。
分析题目
把每样材料拆成 ii 拆开，用 ii 表示满式做法，用 i+ni +n 表示汉式做法。
因为每个评委的要求只要满足一样的即可，所以可以看作是或
点 uu 可以是满/汉式，点 vv 也可以是满/汉式，所以有4种情况：
要求点 uu 是满式 或 点 vv 是满式，那么若 uu 为汉式，则 vv 必为满式；若 vv 为汉式，则 uu 必为满式。
要求点 uu 是满式 或 点 vv 是汉式，那么若 uu 为汉式，则 vv 必为汉式；若 vv 为汉式，则 uu 必为满式。
要求点 uu 是汉式 或 点 vv 是汉式，那么若 uu 为满式，则 vv 必为汉式；若 vv 为满式，则 uu 必为汉式。
要求点 uu 是汉式 或 点 vv 是满式，那么若 uu 为满式，则 vv 必为满式；若 vv 为汉式，则 uu 必为汉式。
建图
从上面的分析，我们可以得出通过特殊建图再跑一边板子2-SAT可以完成这道题。
for (int i = 1; i <= m; ++i) {
string Su, Sv;
cin >> Su >> Sv;
char op1 = Su[0], op2 = Sv[0];
int u = 0, v = 0;
for (int j = 1; j < Su.size(); ++j) u = u * 10 + (Su[j] - '0' + 0);
for (int j = 1; j < Sv.size(); ++j) v = v * 10 + (Sv[j] - '0' + 0);
if (op1 == 'm') {
if (op2 == 'h') add(v, u), add(u + n, v + n); // 第二种情况
else add(u + n, v), add(v + n, u); // 第一种情况
} else {
if (op2 == 'h') add(u, v + n), add(v, u + n); // 第三种情况
else add(u, v), add(v + n, u + n); // 第四种情况
}
}恭喜你这道题做完了。
判断GOOD还是BAD
因为 ii 为满式， i+ni + n 为汉式，所有只要判断 scc[i]==scc[i+n]scc[i] == scc[i+n]就可以了，如果相等就不成立，输出 BAD ，反之输出 GOOD
bool flag = true;
for (int i = 1; i <= n; ++i) {
if (scc[i] == scc[i + n]) {
flag = false;
break;
}
}
cout << (flag ? "GOOD" : "BAD") << "\n";AC代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1000 + 5;
int T;
int n, m;
vector<vector<int>> e;
void add(int u, int v) {
e[u].emplace_back(v);
}
int tot, cnt;
int dfn[2 * N], low[2 * N], scc[2 * N];
stack<int> q;
bitset<2 * N> vis;
void tarjan(int u) {
dfn[u] = low[u] = ++tot;
q.emplace(u);
vis[u] = true;
for (auto v : e[u]) {
if (!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if (vis[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
++cnt;
int v;
do {
v = q.top(); q.pop();
vis[v] = false;
scc[v] = cnt;
} while(v != u);
}
}
void init() {
cnt = tot = 0;
e.clear();
e.resize(2 * N);
stack<int>().swap(q);
vis.reset();
for (int i = 1; i <= 2 * n; ++i) {
dfn[i] = low[i] = scc[i] = 0;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> T;
while (T--) {
init();
cin >> n >> m;
for (int i = 1; i <= m; ++i) {
string Su, Sv;
cin >> Su >> Sv;
char op1 = Su[0], op2 = Sv[0];
int u = 0, v = 0;
for (int j = 1; j < Su.size(); ++j) u = u * 10 + (Su[j] - '0' + 0);
for (int j = 1; j < Sv.size(); ++j) v = v * 10 + (Sv[j] - '0' + 0);
if (op1 == 'm') {
if (op2 == 'h') add(v, u), add(u + n, v + n);
else add(u + n, v), add(v + n, u);
} else {
if (op2 == 'h') add(u, v + n), add(v, u + n);
else add(u, v), add(v + n, u + n);
}
}
for (int i = 1; i <= 2 * n; ++i) if (!dfn[i]) tarjan(i);
bool flag = true;
for (int i = 1; i <= n; ++i) {
if (scc[i] == scc[i + n]) {
flag = false;
break;
}
}
cout << (flag ? "GOOD" : "BAD") << "\n";
}
return 0;
}