题目给定 $n$ 种食材,对于每种食材,有两种制作方法。对于每一种食材,只能用一次,也就是必须恰好选择一种制作方法。一道菜品的信息,同时包括食材和制作方法。
题目给定了 $m$ 条限制,每条限制包含两个菜品的信息。对于每条限制,限制被满足,当且仅当:在给出的两个菜品中,至少有一个菜品被制作出来。
问:是否存在一种菜品制作方法,使得每条限制都被满足?
"> 题目给定 $n$ 种食材,对于每种食材,有两种制作方法。对于每一种食材,只能用一次,也就是必须恰好选择一种制作方法。一道菜品的信息,同时包括食材和制作方法。
题目给定了 $m$ 条限制,每条限制包含两个菜品的信息。对于每条限制,限制被满足,当且仅当:在给出的两个菜品中,至少有一个菜品被制作出来。
问:是否存在一种菜品制作方法,使得每条限制都被满足?
"> Luogu - P4171 - [JSOI2010]满汉全席 - TonyYin - Blog
Luogu – P4171 – [JSOI2010]满汉全席

题意

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

题目给定 $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$,通过分类讨论,可以找到其中这样的关系。

  1. 限制内容:$u$ 为满式,$v$ 为满式。关系:
    • 若 $u$ 为汉式,则 $v$ 必为满式;
    • 若 $v$ 为汉式,则 $u$ 必为汉式。
  2. 限制内容:$u$ 为满式,$v$ 为汉式。关系:
    • 若 $u$ 为汉式,则 $v$ 必为汉式;
    • 若 $v$ 为满式,则 $u$ 必为满式。
  3. 限制内容:$u$ 为汉式,$v$ 为满式。关系:
    • 若 $u$ 为满式,则 $v$ 必为满式;
    • 若 $v$ 为汉式,则 $u$ 必为汉式。
  4. 限制内容:$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;
}

 

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇