BZOJ 1823 [JSOI2010]满汉全席题解

Description

满汉全席是中国最丰盛的宴客菜肴，有许多种不同的材料透过满族或是汉族的料理方式，呈现在數量繁多的菜色之中。由于菜色众多而繁杂，只有极少數博学多闻技艺高超的厨师能够做出满汉全席，而能够烹饪出经过专家认证的满汉全席，也是中国厨师最大的荣誉之一。 世界满汉全席协会是由能够料理满汉全席的专家厨师们所组成，而他们之间还细分为许多不同等级的厨师。为了招收新进的厨师进入世界满汉全席协会，将于近日举办满汉全席大赛，协会派遣许多会员当作评审员，为的就是要在參赛的厨师之中，找到满汉料理界的明日之星。 大会的规则如下：每位參赛的选手可以得到n 种材料，选手可以*选择用满式或是汉式料理将材料当成菜肴。大会的评审制度是：共有m 位评审员分别把关。每一位评审员对于满汉全席有各自独特的見解，但基本见解是，要有兩样菜色作为满汉全席的标志。如某评审认为，如果没有汉式东坡肉跟满式的涮羊肉锅，就不能算是满汉全席。但避免过于有主見的审核，大会规定一个评审员除非是在认为必备的两样菜色都没有做出來的狀况下，才能淘汰一位选手，否则不能淘汰一位參赛者。换句话說，只要參赛者能在这兩种材料的做法中，其中一个符合评审的喜好即可通过该评审的审查。如材料有猪肉，羊肉和牛肉时，有四位评审员的喜好如下表： 评审一 评审二 评审三 评审四 满式牛肉 满式猪肉 汉式牛肉 汉式牛肉 汉式猪肉 满式羊肉 汉式猪肉 满式羊肉 如參赛者甲做出满式猪肉，满式羊肉和满式牛肉料理，他将无法满足评审三的要求，无法通过评审。而參赛者乙做出汉式猪肉，满式羊肉和满式牛肉料理，就可以满足所有评审的要求。 但大会后來发现，在这样的制度下如果材料选择跟派出的评审员没有特别安排好的话，所有的參赛者最多只能通过部分评审员的审查而不是全部，所以可能会发生没有人通过考核的情形。如有四个评审员喜好如下表时，则不論參赛者采取什么样的做法，都不可能通过所有评审的考核： 评审一 评审二 评审三 评审四 满式羊肉 满式猪肉 汉式羊肉 汉式羊肉 汉式猪肉 满式羊肉 汉式猪肉 满式猪肉 所以大会希望有人能写一个程序來判断，所选出的m 位评审，会不会发生 没有人能通过考核的窘境，以便协会组织合适的评审团。

---

Input

第一行包含一个数字 K，代表测试文件包含了K 组资料。每一组测试资料的第一行包含兩个数字n 跟m（n≤100，m≤1000），代表有n 种材料，m 位评审员。为方便起見，材料舍弃中文名称而给予编号，编号分别从1 到n。接下來的m 行，每行都代表对应的评审员所拥有的兩个喜好，每个喜好由一个英文字母跟一个数字代表，如m1 代表这个评审喜欢第1 个材料透过满式料理做出來的菜，而h2 代表这个评审员喜欢第2 个材料透过汉式料理做出來的菜。每个测试文件不会有超过50 组测试资料

---

Output

每笔测试资料输出一行，如果不会发生没有人能通过考核的窘境，输出GOOD；否则输出BAD（大写字母）。

---

Sample Input

2

3 4

m3 h1

m1 m2

h1 h3

h3 m2

2 4

h1 m2

m2 m1

h1 h2

m1 h2

---

Sample Output

GOOD

BAD

---

题解：

显然是一道最裸的2-SAT模型，考试的时候遇到还真有点麻烦，总之拆点就行了，把一个食材拆成两道菜，一道汉菜一道满菜，然后如果一个评委的要求是食材a的满菜和食材b的汉菜，那么就把食材a的汉菜向食材b的汉菜连一条边，食材b的满菜向食材a的满菜连一条边，原因是如果选了食材a的汉菜，那么一定要选择食材b的汉菜，要不然就会被淘汰，这道题太水了，连方案都不用输出，也就是说直接建图然后tarjan一遍，最后再判断同一个食材的两个菜是否都被选中了（也就是说处于一个强连通分量里，选该食材的满菜就得选该食材的汉菜，或者选该食材的汉菜就得选该食材的满菜，这样都是不合法的），因此只需要这样判断一下就好了
一定要注意的是…这个读入，简直有毒…被读入卡了好久，大家写的时候仔细检查读入，还有就是用cin来读字符，不要用ios::sync_with _ stdio(false)，会出错

#include<cstdio>
#include<iostream>
#include<cstring> 
#define MAXN 5000
using namespace std;
struct Line{
int from,to,nxt;
}line[MAXN];
int head[MAXN],tail;
int dfn[MAXN],low[MAXN],stack[MAXN],top,cnt,scc[MAXN],timer;
bool vis[MAXN];
int T,n,m;  
char a,b; 
void add_line(int from,int to){
    tail++;
    line[tail].from=from;
    line[tail].to=to;
    line[tail].nxt=head[from];
    head[from]=tail;
}
void tarjan(int u){
    dfn[u]=low[u]=++timer;
    vis[u]=true;
stack[++top]=u;
for(register int i=head[u];i;i=line[i].nxt){
int v=line[i].to;
if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }else if(vis[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
if(dfn[u]==low[u]){
        vis[u]=false;
        cnt++;
        scc[u]=cnt;
while(stack[top]!=u){
            vis[stack[top]]=false;
            scc[stack[top]]=cnt;
            top--;
        }
        top--;
    }
}

int main(){
//ios::sync_with_stdio(false);
//freopen("sat.txt","r",stdin);
cin>>T;
while(T--){
cin>>n>>m;//n份食材,m个评委,满为偶数,汉为奇数(2*n为汉,2*n+1为满) 
int N=2*n;//一共2*n种菜,每种菜可以选或者不选 
for(register int i=0;i<=N;i++) dfn[i]=low[i]=head[i]=0;
        cnt=0;timer=0;top=0;tail=0;
for(register int i=1;i<=m;i++){
int x,y;
int c,d;
cin>>a;
scanf("%d",&x);
cin>>b;
scanf("%d",&y);  
if(a=='h')x=x*2-1;else x=x*2;
if(b=='h')y=y*2-1;else y=y*2;
if(a=='h')c=x+1;else c=x-1;
if(b=='h')d=y+1;else d=y-1;
            add_line(c,y);add_line(d,x);
        }
for(register int i=1;i<=N;i++){
if(!dfn[i]) tarjan(i);
        }
bool judge=false;
for(register int i=1;i<=n;i++){
if(scc[i<<1]==scc[(i<<1)-1]){
printf("BAD\n");
                judge=true;
break;
            } 
        }
if(!judge) printf("GOOD\n");
    }
return 0;
}