[Luogu P4171] [BZOJ 1823] [JSOI2010]满汉全席

xiaoxiao2021-02-28  71

洛谷传送门

BZOJ传送门

题目描述

满汉全席是中国最丰盛的宴客菜肴,有许多种不同的材料透过满族或是汉族的料理方式,呈现在數量繁多的菜色之中。由于菜色众多而繁杂,只有极少數博学多闻技艺高超的厨师能够做出满汉全席,而能够烹饪出经过专家认证的满汉全席,也是中国厨师最大的荣誉之一。世界满汉全席协会是由能够料理满汉全席的专家厨师们所组成,而他们之间还细分为许多不同等级的厨师。

为了招收新进的厨师进入世界满汉全席协会,将于近日举办满汉全席大赛,协会派遣许多会员当作评审员,为的就是要在參赛的厨师之中,找到满汉料理界的明日之星。

大会的规则如下:每位參赛的选手可以得到 n n 种材料,选手可以自由选择用满式或是汉式料理将材料当成菜肴。

大会的评审制度是:共有 mm 位评审员分别把关。每一位评审员对于满汉全席有各自独特的見解,但基本见解是,要有兩样菜色作为满汉全席的标志。如某评审认为,如果没有汉式东坡肉跟满式的涮羊肉锅,就不能算是满汉全席。但避免过于有主見的审核,大会规定一个评审员除非是在认为必备的两样菜色都没有做出來的狀况下,才能淘汰一位选手,否则不能淘汰一位參赛者。

换句话說,只要參赛者能在这兩种材料的做法中,其中一个符合评审的喜好即可通过该评审的审查。如材料有猪肉,羊肉和牛肉时,有四位评审员的喜好如下表:

评审一 评审二 评审三 评审四 满式牛肉 满式猪肉 汉式牛肉 汉式牛肉 汉式猪肉 满式羊肉 汉式猪肉 满式羊肉

如參赛者甲做出满式猪肉,满式羊肉和满式牛肉料理,他将无法满足评审三的要求,无法通过评审。而參赛者乙做出汉式猪肉,满式羊肉和满式牛肉料理,就可以满足所有评审的要求。

但大会后來发现,在这样的制度下如果材料选择跟派出的评审员没有特别安排好的话,所有的參赛者最多只能通过部分评审员的审查而不是全部,所以可能会发生没有人通过考核的情形。

如有四个评审员喜好如下表时,则不论参赛者采取什么样的做法,都不可能通过所有评审的考核:

评审一 评审二 评审三 评审四 满式羊肉 满式猪肉 汉式羊肉 汉式羊肉 汉式猪肉 满式羊肉 汉式猪肉 满式猪肉

所以大会希望有人能写一个程序來判断,所选出的 m m 位评审,会不会发生 没有人能通过考核的窘境,以便协会组织合适的评审团。

输入输出格式

输入格式:

第一行包含一个数字 KK,代表测试文件包含了 K K 组资料。

每一组测试资料的第一行包含兩个数字 nn m m n100m1000n≤100,m≤1000),代表有 n n 种材料,mm 位评审员。

为方便起見,材料舍弃中文名称而给予编号,编号分别从 1 1 nn

接下來的 m m 行,每行都代表对应的评审员所拥有的兩个喜好,每个喜好由一个英文字母跟一个数字代表,如 m1m1 代表这个评审喜欢第 1 1 个材料透过满式料理做出來的菜,而 h2h2 代表这个评审员喜欢第 2 2 个材料透过汉式料理做出來的菜。

每个测试文件不会有超过 5050 组测试资料

输出格式:

每笔测试资料输出一行,如果不会发生没有人能通过考核的窘境,输出 GOOD G O O D ;否则输出 BAD B A D (大写字母)。

输入输出样例

输入样例#1:

2 3 4 m3 h1 m1 m2 h1 h3 h3 m2 2 4 h1 m2 m2 m1 h1 h2 m1 h2

输出样例#1:

GOOD BAD

解题分析

因为每种材料只能做成两种菜,考虑2-SAT。将每个材料拆成两个点分别表示做成汉式菜肴还是做成满式菜肴, 暴力连边跑 tarjan t a r j a n 缩点即可。 如果两个点在同一 SCC S C C 中则说明不合法,输出 BAD B A D

细节见代码

#include <cstdio> #include <algorithm> #include <cstdlib> #include <cctype> #include <cmath> #include <cstring> #define R register #define IN inline #define W while #define gc getchar() #define MX 1050 template <class T> IN void in(T &x) { x = 0; R char c = gc; W (!isdigit(c)) c = gc; W (isdigit(c)) x = (x << 1) + (x << 3) + c - 48, c = gc; } IN bool get(int &x) { x = 0; R char c = gc; bool ret; W (!isdigit(c)) { if(c == 'h') ret = true; if(c == 'm') ret = false; c = gc; } W (isdigit(c)) x = (x << 1) + (x << 3) + c - 48, c = gc; return ret; } int T, dot, man, v1, v2, arr, top, col, cnt; int head[MX], bel[MX], sta[MX], dfn[MX], low[MX]; bool vis[MX], g1, g2; struct Edge { int to, nex; }edge[MX << 1]; IN void addedge(const int &from, const int &to) { edge[++cnt] = {to, head[from]}; head[from] = cnt; } void tarjan(const int &now) { dfn[now] = low[now] = ++arr; sta[++top] = now, vis[now] = true; for (R int i = head[now]; i; i = edge[i].nex) { if(!dfn[edge[i].to]) tarjan(edge[i].to), low[now] = std::min(low[now], low[edge[i].to]); else if(vis[edge[i].to]) low[now] = std::min(low[now], dfn[edge[i].to]); } if(dfn[now] == low[now]) { R int tp = 0; ++col; W (tp != now) { tp = sta[top--]; bel[tp] = col; vis[tp] = false; } } } int main(void) { in(T); int bd; W (T--) { in(dot), in(man); std::memset(head, arr = cnt = 0, sizeof(head)); std::memset(dfn, col = 0, sizeof(dfn)); bd = dot * 2; for (R int i = 1; i <= man; ++i) { g1 = get(v1); g2 = get(v2); if(g1 && g2) addedge(v2 + dot, v1), addedge(v1 + dot, v2); else if(g1 && !g2) addedge(v1 + dot, v2 + dot), addedge(v2, v1); else if(!g1 && g2) addedge(v1, v2), addedge(v2 + dot, v1 + dot); else addedge(v1, v2 + dot), addedge(v2, v1 + dot); } for (R int i = 1; i <= bd; ++i) if(!dfn[i]) tarjan(i); for (R int i = 1; i <= dot; ++i) if(bel[i] == bel[i + dot]) goto err; printf("GOOD\n"); continue; err :; printf("BAD\n"); } }
转载请注明原文地址: https://www.6miu.com/read-2350249.html

最新回复(0)