P4171 [JSOI2010] 满汉全席
大意
要求判断是否满足多对需求。
思路
显然，对于每个评委，他的两个要求你至少要完成一个菜，那么我们显然就有这样的连边：
定义 \(u \times 2\) 表示 \(u\) 这个点采用汉式做法，\(u \times 2 + 1\) 表示这个点采用满式做法。
那么对于我们给的两个玩意就可以分成 \(4\) 种情况讨论：
\[\begin{cases}
\begin{cases}
u \times 2 \to v \times 2, \\
v \times 2 + 1 \to u \times 2 + 1
\end{cases} & u = \text{'m'} \land v = \text{'h'}, \\
\begin{cases}
u \times 2 \to v \times 2 + 1, \\
v \times 2 \to u \times 2 + 1
\end{cases} & u = \text{'m'} \land v = \text{'m'}, \\
\begin{cases}
u \times 2 + 1 \to v \times 2, \\
v \times 2 + 1 \to u \times 2
\end{cases} & u = \text{'h'} \land v = \text{'h'}, \\
\begin{cases}
u \times 2 + 1 \to v \times 2 + 1, \\
v \times 2 \to u \times 2
\end{cases} & u = \text{'h'} \land v = \text{'m'}
\end{cases}
\]
然后就直接正常跑 \(\text{2 - SAT}\) 即可。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 200;
int n, m, S[N * 2], c;
bool selected[N * 2];
vector<int> g[N * 2];
bool dfs(int u) {if (selected[u ^ 1]) {return false;}if (selected[u]) {return true;}selected[u] = true;S[c++] = u;for (int i = 0; i < g[u].size(); i++) {int v = g[u][i];if (!dfs(v)) {return false;}}return true;
}
bool Two_SAT() {for (int i = 0; i < 2 * n; i += 2) {if (!selected[i] && !selected[i + 1]) {c = 0;if (!dfs(i)) {while (c > 0) {selected[S[--c]] = false;}if (!dfs(i + 1)) {return false;}}}}return true;
}
int main() {int T, u, v;cin >> T;while (T--) {cin >> n >> m;for (int i = 0; i < n * 2; i++) {g[i].clear();}memset(selected, 0, sizeof(selected));for (int i = 1; i <= m; i++) {char o1, o2;cin >> o1 >> u >> o2 >> v;u--, v--;if (o1 == 'm') {if (o2 == 'h') {g[u * 2].push_back(v * 2);g[v * 2 + 1].push_back(u * 2 + 1);} else if (o2 == 'm') {g[u * 2].push_back(v * 2 + 1);g[v * 2].push_back(u * 2 + 1);}} else if (o1 == 'h') {if (o2 == 'h') {g[u * 2 + 1].push_back(v * 2);g[v * 2 + 1].push_back(u * 2);} else if (o2 == 'm') {g[u * 2 + 1].push_back(v * 2 + 1);g[v * 2].push_back(u * 2);}}}if (Two_SAT()) {cout << "GOOD" << endl;} else {cout << "BAD" << endl;}}return 0;
}