前置知识：2-SAT

题目大意

有 n 种材料，每种可做满式（m）或汉式（h）。m 位评审各有两个喜好（如 m1、h2），只要选手做出其中一个喜好的菜，该评审就通过。

问：是否存在一种做菜方案，能让所有评审都通过？

存在输出 GOOD，否则输出 BAD。

解题思路

显然这是一道2-SAT裸题。

分析题目

把每样材料拆成 $i$ 拆开，用 $i$ 表示满式做法，用 $i +n$ 表示汉式做法。

因为每个评委的要求只要满足一样的即可，所以可以看作是或

点 $u$ 可以是满/汉式，点 $v$ 也可以是满/汉式，所以有4种情况：

要求点 $u$ 是满式或点 $v$ 是满式，那么若 $u$ 为汉式，则 $v$ 必为满式；若 $v$ 为汉式，则 $u$ 必为满式。
要求点 $u$ 是满式或点 $v$ 是汉式，那么若 $u$ 为汉式，则 $v$ 必为汉式；若 $v$ 为汉式，则 $u$ 必为满式。
要求点 $u$ 是汉式或点 $v$ 是汉式，那么若 $u$ 为满式，则 $v$ 必为汉式；若 $v$ 为满式，则 $u$ 必为汉式。
要求点 $u$ 是汉式或点 $v$ 是满式，那么若 $u$ 为满式，则 $v$ 必为满式；若 $v$ 为汉式，则 $u$ 必为汉式。

建图

从上面的分析，我们可以得出通过特殊建图再跑一边板子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

因为 $i$ 为满式， $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;
}

P4171 [JSOI2010] 满汉全席 2-SAT详细题解

题目大意

解题思路

分析题目

建图

判断GOOD还是BAD

AC代码

评论区