题意:有n种材料,每种材料可以被做成汉式菜肴和满式菜肴中的一种,有m个评委,每个评委喜欢两种菜肴(汉式和满式任意,材料任意),求能否做两个菜肴使得满足每个评委的至少一个条件.(\(n<=100,m<=1000\)).
分析:这道题挺妙的,众所周知,\(2-SAT\)问题的难点就是建图,本题很好地体现了这一点.显然,n个材料就是n个点,m个评委就有m个要求,对于每个点(材料)我们要拆成4个点,分别是满式做,满式不做,汉式做,汉式不做.然后再根据题意连边,跑tarjan即可.
代码中对于一个点\(a\),\(a\)表示满不做,\(a+n\)满做,\(a+2*n\)汉不做,\(a+3*n\)汉做.
#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>#include<queue>#include<map>#include<set>#define ll long longusing namespace std;inline int read(){ int x=0,o=1;char ch=getchar(); while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar(); if(ch=='-')o=-1,ch=getchar(); while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*o;}const int N=505;const int M=10005;int tot,head[N],nxt[M],to[M];inline void add(int a,int b){ nxt[++tot]=head[a];head[a]=tot;to[tot]=b;}int top,tim,num,dfn[N],low[N],st[N],color[N];inline void tarjan(int u){ dfn[u]=low[u]=++tim;st[++top]=u; for(int i=head[u];i;i=nxt[i]){ int v=to[i]; if(!dfn[v]){ tarjan(v); low[u]=min(low[u],low[v]); } else if(!color[v]){ low[u]=min(low[u],dfn[v]); } } if(low[u]==dfn[u]){ color[u]=++num; while(st[top]!=u){ color[st[top]]=num; --top; } --top; }}int main(){ int T;cin>>T; while(T--){ tot=0;top=0;tim=0;num=0; int n,m;cin>>n>>m; for(int i=1;i<=4*n;++i){ head[i]=color[i]=0; dfn[i]=low[i]=0; }//多组数据初始化 for(int i=1;i<=m;++i){ string s1,s2;cin>>s1>>s2; int a=0,b=0,j=1; while(s1[j]>='0'&&s1[j]<='9')a=a*10+s1[j]-'0',++j; j=1;while(s2[j]>='0'&&s2[j]<='9')b=b*10+s2[j]-'0',++j; if(s1[0]=='m'){//大力分类讨论 if(s2[0]=='m'){ add(a,b+n);add(b,a+n); } else if(s2[0]=='h'){ add(a,b+3*n);add(b+2*n,a+n); } } else if(s1[0]=='h'){ if(s2[0]=='m'){ add(a+2*n,b+n);add(b,a+3*n); } else if(s2[0]=='h'){ add(a+2*n,b+3*n);add(b+2*n,a+3*n); } } } for(int i=1;i<=n;++i){ add(i+n,i+2*n);add(i+3*n,i); }//别忽略了这个,每个点(材料)最多只能做成一个菜肴,不能既满又汉 for(int i=1;i<=n*4;++i)if(!dfn[i])tarjan(i); int bj=1; for(int i=1;i<=n;++i){ if(color[i]==color[i+n]||color[i+2*n]==color[i+3*n]||color[i+n]==color[i+3*n]){ puts("BAD");bj=0;break; } }//判断条件也有很多了. if(bj)puts("GOOD"); } return 0;}
