原文链接http://www.cnblogs.com/zhouzhendong/p/8125944.html
题意概括
有n道菜，分别可以做成满式和汉式（每道菜只能做成一种形式），有m个专家。
每个专家喜欢两种菜，比如汉式猪肉和满式牛肉。
问是否存在方案使得所有专家都被满足。
题解
2-sat模版题，连方案都不用输出，水过……
代码
#include#include #include #include #include using namespace std;bool isd(char ch){ return '0'<=ch&&ch<='9';}int read(){ int res=0; char ch=getchar(); while (!isd(ch)) ch=getchar(); while (isd(ch)) res=(res<<1)+(res<<3)+ch-48,ch=getchar(); return res;}char getc(){ char ch=getchar(); while (!('a'<=ch&&ch<='z')&&!isd(ch)) ch=getchar(); return ch;}const int N=105*2,M=1005*2;struct Gragh{ int cnt,y[M],nxt[M],fst[N]; void clear(){ cnt=0; memset(fst,0,sizeof fst); } void add(int a,int b){ y[++cnt]=b,nxt[cnt]=fst[a],fst[a]=cnt; }}g;int T,n,m;int get_dish(){ char ch=getc(); int v=read(); return v+n*(ch=='m');}int calc(int x){ return x+n*(x<=n?1:-1);}int dfn[N],low[N],vis[N],st[N],inst[N],top,time,cnt,bh[N];void Tarjan_Prepare(){ top=time=cnt=0; memset(inst,0,sizeof inst); memset(vis,0,sizeof vis); memset(dfn,0,sizeof dfn); memset(low,0,sizeof low); memset(st,0,sizeof st); memset(bh,0,sizeof bh);}void Tarjan(int x){ dfn[x]=low[x]=++time; st[++top]=x; inst[x]=vis[x]=1; for (int i=g.fst[x];i;i=g.nxt[i]) if (!vis[g.y[i]]){ Tarjan(g.y[i]); low[x]=min(low[x],low[g.y[i]]); } else if (inst[g.y[i]]) low[x]=min(low[x],low[g.y[i]]); if (dfn[x]==low[x]){ cnt++; bh[st[top]]=cnt; inst[st[top]]=0; while (st[top--]!=x){ bh[st[top]]=cnt; inst[st[top]]=0; } }}bool check(){ for (int i=1;i<=n;i++) if (bh[i]==bh[i+n]) return 0; return 1;}int main(){ T=read(); while (T--){ n=read(),m=read(); g.clear(); for (int i=1;i<=m;i++){ int a=get_dish(),b=get_dish(); g.add(a,calc(b)); g.add(b,calc(a)); } Tarjan_Prepare(); for (int i=1;i<=n*2;i++) if (!vis[i]) Tarjan(i); puts(check()?"GOOD":"BAD"); } return 0;}