题解 P4171 【[JSOI2010]满汉全席】
钱逸凡
2018-09-05 13:39:30
很明显的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;
}
```