題目描述

滿漢全席是中國最豐盛的宴客菜肴，有許多種不同的材料透過滿族或是漢族的料理方式，呈現在數量繁多的菜色之中。由于菜色眾多而繁雜，只有極少數博學多聞技藝高超的廚師能夠做出滿漢全席，而能夠烹飪出經過專家認證的滿漢全席，也是中國廚師最大的榮譽之一。世界滿漢全席協會是由能夠料理滿漢全席的專家廚師們所組成，而他們之間還細分為許多不同等級的廚師。

為了招收新進的廚師進入世界滿漢全席協會，將于近日舉辦滿漢全席大賽，協會派遣許多會員當作評審員，為的就是要在參賽的廚師之中，找到滿漢料理界的明日之星。

大會的規則如下：每位參賽的選手可以得到n 種材料，選手可以自由選擇用滿式或是漢式料理將材料當成菜肴。

大會的評審制度是：共有m 位評審員分別把關。每一位評審員對于滿漢全席有各自獨特的見解，但基本見解是，要有兩樣菜色作為滿漢全席的標志。如某評審認為，如果沒有漢式東坡肉跟滿式的涮羊肉鍋，就不能算是滿漢全席。但避免過于有主見的審核，大會規定一個評審員除非是在認為必備的兩樣菜色都沒有做出來的狀況下，才能淘汰一位選手，否則不能淘汰一位參賽者。

換句話說，只要參賽者能在這兩種材料的做法中，其中一個符合評審的喜好即可通過該評審的審查。如材料有豬肉，羊肉和牛肉時，有四位評審員的喜好如下表：

評審一 評審二 評審三 評審四?
滿式牛肉 滿式豬肉 漢式牛肉 漢式牛肉?
漢式豬肉 滿式羊肉 漢式豬肉 滿式羊肉?

如參賽者甲做出滿式豬肉，滿式羊肉和滿式牛肉料理，他將無法滿足評審三的要求，無法通過評審。而參賽者乙做出漢式豬肉，滿式羊肉和滿式牛肉料理，就可以滿足所有評審的要求。

但大會后來發現，在這樣的制度下如果材料選擇跟派出的評審員沒有特別安排好的話，所有的參賽者最多只能通過部分評審員的審查而不是全部，所以可能會發生沒有人通過考核的情形。

如有四個評審員喜好如下表時，則不論參賽者采取什么樣的做法，都不可能通過所有評審的考核：

評審一 評審二 評審三 評審四?
滿式羊肉 滿式豬肉 漢式羊肉 漢式羊肉?
漢式豬肉 滿式羊肉 漢式豬肉 滿式豬肉?

所以大會希望有人能寫一個程序來判斷，所選出的m 位評審，會不會發生 沒有人能通過考核的窘境，以便協會組織合適的評審團。

輸入輸出格式

輸入格式：

第一行包含一個數字 K，代表測試文件包含了K 組資料。

每一組測試資料的第一行包含兩個數字n 跟m（n≤100，m≤1000），代表有n 種材料，m 位評審員。

為方便起見，材料舍棄中文名稱而給予編號，編號分別從1 到n。

接下來的m 行，每行都代表對應的評審員所擁有的兩個喜好，每個喜好由一個英文字母跟一個數字代表，如m1 代表這個評審喜歡第1 個材料透過滿式料理做出來的菜，而h2 代表這個評審員喜歡第2 個材料透過漢式料理做出來的菜。

每個測試文件不會有超過50 組測試資料

輸出格式：

每筆測試資料輸出一行，如果不會發生沒有人能通過考核的窘境，輸出GOOD；否則輸出BAD（大寫字母）。

輸入輸出樣例

輸入樣例#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

思路：

對于每組數據，將 n 個材料拆分為兩個點，用 i?來表示為滿式，用 i+n?來表示為漢式，0、1 來表示不選擇與選擇，根據評委的限制條件，對于兩個材料 a、b 有：

• 當 a 是滿式時，則 b 必為漢式，有：<a,0,b,0>、<b,1,a,1>，即連邊 (a+n,b+n)、(b,a)
• 當 a 是滿式時，則 b 必為滿式，有：<a,0,b,1>、<b,0,a,1>，即連邊 (a+n,b)、(b+n,a)
• 當 a 是漢式時，則 b 必為漢式，有：<a,1,b,0>、<b,1,a,0>，即連邊 (a,b+n)、(b,a+n)
• 當 a?是漢式時，則 b 必為滿式，有：<a,1,b,1>、<b,0,a,0>，即連邊 (a,b)、(b+n,a+n)

建完圖后，跑一遍 2-SAT 的版子即可

源代碼

#include<iostream> #include<cstdio> #include<cstdlib> #include<string> #include<cstring> #include<cmath> #include<ctime> #include<algorithm> #include<utility> #include<stack> #include<queue> #include<vector> #include<set> #include<map> #include<bitset> #define Exp 1e-9 #define PI acos(-1.0) #define INF 0x3f3f3f3f #define LL long long const int MOD = 1E9+7; const int N = 1000000+5; const int dx[] = {-1,1,0,0,-1,-1,1,1}; const int dy[] = {0,0,-1,1,-1,1,-1,1}; using namespace std;struct Edge{int to,next; }edge[N*2]; int head[N],tot; int n,m; int dfn[N],low[N]; bool vis[N];//標記數組 int scc[N];//記錄結點i屬于哪個強連通分量 int block_cnt;//時間戳 int sig;//記錄強連通分量個數 stack<int> S; void init(){tot=0;sig=0;block_cnt=0;memset(head,-1,sizeof(head));memset(vis,0,sizeof(vis));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(scc,0,sizeof(scc)); } void addEdge(int from,int to){edge[++tot].to=to;edge[tot].next=head[from];head[from]=tot; } void Tarjan(int x) {vis[x]=true;dfn[x]=low[x]=++block_cnt;//每找到一個新點，紀錄當前節點的時間戳S.push(x);//當前結點入棧for(int i=head[x]; i!=-1; i=edge[i].next) { //遍歷整個棧int y=edge[i].to;//當前結點的下一結點if(!dfn[y]) {Tarjan(y);low[x]=min(low[x],low[y]);}else if(vis[y])low[x]=min(low[x],dfn[y]);}if(dfn[x]==low[x]) { //滿足強連通分量要求sig++;//記錄強連通分量個數while(true) { //記錄元素屬于第幾個強連通分量int temp=S.top();S.pop();vis[temp]=false;scc[temp]=sig;if(temp==x)break;}} } bool twoSAT(){for(int i=1;i<=2*n;i++)//找強連通分量if(!dfn[i])Tarjan(i);for(int i=1;i<=n;i++)if(scc[i]==scc[i+n])//條件a與!a屬于同一連通分量，無解return false;return true; } int main() {int t;scanf("%d",&t);while(t--){init();scanf("%d%d",&n,&m);while(m--) {char s1[10],s2[10];scanf("%s%s",s1,s2);int a=0,b=0;int k=1;while(s1[k]>='0'&&s1[k]<='9')a=a*10+(s1[k++]-'0');k=1;while(s2[k]>='0'&&s2[k]<='9')b=b*10+(s2[k++]-'0');if(s1[0]=='m'){if(s2[0]=='h'){addEdge(a+n,b+n);addEdge(b,a);}else if(s2[0]=='m'){addEdge(a+n,b);addEdge(b+n,a);}}else if(s1[0]=='h'){if(s2[0]=='h'){addEdge(a,b+n);addEdge(b,a+n);}else if(s2[0]=='m'){addEdge(a,b);addEdge(b+n,a+n);}}}bool flag=twoSAT();if(!flag)printf("BAD\n");elseprintf("GOOD\n");}return 0; }

?

總結

以上是生活随笔為你收集整理的满汉全席（洛谷-P4171）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。