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

很明显的2-SAT，[建议先看看2-SAT模板](https://www.luogu.org/problemnew/show/P4782) 每种食材有两个状态：汉式或满式。这对应了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; } ```