题解 P4171 【[JSOI2010]满汉全席】

2018-09-05 13:39:30


很明显的2-SAT,建议先看看2-SAT模板

每种食材有两个状态:汉式或满式。这对应了2-SAT模版里的真或假。

只要參赛者能在这兩种材料的做法中,其中一个符合评审的喜好即可通过该评审的审查。

每个评审员对应2-SAT模版里的一个条件:a为真/假或b为真/假满足其中之一。

然后这就是一道2-SAT的模板了。

建图:如果某评审为m3 ,h1(m3对应条件a,h1对应条件b)(样例第一个数据),我们可以这样连边:h3连向h1,m1连向m3(非a连向b,非b连向a)。

然后像2-SAT一样,跑tarjan判强联通分类即可。

注意:多组数据清空数组

代码:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int T,n,m;
int head[1010],top;
struct Node{
    int v;
    int next;
}node[2020];
inline void addedge(int u,int v){
    node[++top].v=v;
    node[top].next=head[u];
    head[u]=top;
}
int taj,cnt,t,belong[1010],dfn[1010],low[1010],st[1010];
bool inst[1010];
int a1,a2;
inline void Read(int &a){
    a=0;
    int f=0;
    char c=getchar();
    while(c!='m'&&c!='h')c=getchar();
    if(c=='h')a=n;//i代表满式,i+n代表汉式
    c=getchar(); 
    while(c>='0'&&c<='9')f=f*10+c-'0',c=getchar();
    a+=f;
}//读入对应食材 
void tarjan(int u){
    dfn[u]=low[u]=++t;
    st[cnt++]=u;
    inst[u]=1;
    for(int i=head[u];i;i=node[i].next){
        int d=node[i].v;
        if(dfn[d]==-1){
            tarjan(d);
            low[u]=min(low[u],low[d]);
        }
        else if(inst[d])low[u]=min(low[u],low[d]);
    }
    if(dfn[u]==low[u]){
        taj++;
        int now;
        do{
            now=st[--cnt];
            inst[now]=0;
            belong[now]=taj;
        }while(now!=u);
    }
}
int main(){
    scanf("%d",&T);
    int fa1,fa2;
    register int i;
    while(T--){
        scanf("%d %d",&n,&m);
        taj=cnt=t=top=0;
        memset(dfn,-1,sizeof(dfn));
        memset(low,-1,sizeof(low));
        memset(head,0,sizeof(head));
        memset(node,0,sizeof(node));
        memset(st,0,sizeof(st));
        memset(inst,0,sizeof(inst));
        memset(belong,0,sizeof(belong));
        for(i=1;i<=m;i++){
        Read(a1),Read(a2);
        fa1=a1<=n?a1+n:a1-n;//非a1 
        fa2=a2<=n?a2+n:a2-n;//非a2 
        addedge(fa1,a2);
        addedge(fa2,a1);
        }
        bool f=0;
        for(i=1;i<=n*2;i++)if(dfn[i]==-1)tarjan(i);
        for(i=1;i<=n;i++){
            if(belong[i]==belong[i+n]){
                f=1;
                break;
            }
        }
        if(f==0)printf("GOOD\n");
        else printf("BAD\n");
    }
    return 0;
}