【洛谷-P4171】[JSOI2010]满汉全席 • TonyYin's Blog

题意#

题面比较长，先概括一下。如果感觉题目没有完全看懂，建议先看一下下面的要点概括。

题目给定了 $n$ 种食材，对于每种食材，有两种制作方法。对于每一种食材，只能用一次，也就是必须恰好选择一种制作方法。一道菜品的信息，同时包括食材和制作方法。

题目给定了 $m$ 条限制，每条限制包含两个菜品的信息。对于每条限制，限制被满足，当且仅当：在给出的两个菜品中，至少有一个菜品被制作出来。

题目问：是否存在一种菜品制作方法，使得每条限制都被满足。

题目有多组询问，询问次数 $T\leq 50$ ，食材个数 $n\leq 100$ ，限制条数 $m\leq 1000$ .

分析#

看到每种食材必须在两种制作方法中，恰好选择一种，想到 2-SAT 算法。

对于每种食材，将两种制作方式拆成两个点。具体地，代表满式做法的点编号为 $[1, n]$ ，代表汉式做法的点编号为 $[n + 1, 2n]$ .

因为要用到 2-SAT，我们需要找到形如 $a \land b = 0$ 且 $a \lor b = 1$ 这样 的关系。

对于限制条件给定的两个菜品 $u, v$ ，通过分类讨论，可以找到其中这样的关系。

限制内容： $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 即可。如果你不会 2-SAT，可以参考：Anguei 的博客 - 2-SAT 问题 ↗。

代码#

为了缩短长度，代码中删除了 $\rm{I/O}$ 部分，自行补上即可。

#include <bits/stdc++.h>
using namespace std;
/*
折叠了快速读入和输出部分
*/
const int MAXN = 1e6 + 10, MAXM = 1e6 + 10;
int n, m;
struct Edge{
	int to, nxt;
}edge[MAXM << 1];
int head[MAXN << 1], e_cnt = 0;
void add_edge(int u, int v) {
	edge[++e_cnt].to = v;
	edge[e_cnt].nxt = head[u];
	head[u] = e_cnt;
}
int low[MAXN << 1], dfn[MAXN << 1], tot = 0, st[MAXN << 1], top = 0, vis[MAXN << 1];
int col[MAXN << 1], scc = 0;
void Tarjan(int x) {
	low[x] = dfn[x] = ++tot;
	st[++top] = x; vis[x] = true;
	for(int i = head[x]; i; i = edge[i].nxt) {
		int v = edge[i].to;
		if(!dfn[v]) {
			Tarjan(v); low[x] = min(low[x], low[v]);
		} else if(vis[v]) {
			low[x] = min(low[x], dfn[v]);
		}
	}
	if(dfn[x] == low[x]) {
		col[x] = ++scc;
		int y;
		do {
			y = st[top--]; vis[y] = false;
			col[y] = scc;
		} while(x != y);
	}
}
int main() {
	n = read(); m = read();
	for(int i = 1; i <= m; i++) {
		int a = read(), va = read(), b = read(), vb = read(); 
		//a或b：连边方式为 (a->非b), (b->非a)
		add_edge(a + n * (va & 1), b + n * (vb ^ 1));
		add_edge(b + n * (vb & 1), a + n * (va ^ 1));
	}
	for(int i = 1; i <= (n << 1); i++) {
		if(!dfn[i]) Tarjan(i);
	}
	for(int i = 1; i <= (n << 1); i++) {
		if(col[i] == col[i + n]) {
			cout << "IMPOSSIBLE\n" << endl;
			return 0;
		}
	}
	cout << "POSSIBLE\n";
	for(int i = 1; i <= n; i++) {
		out(col[i] < col[i + n]); putchar(' ');
	}
	putchar('\n');
	return 0;
}

cpp