原文链接http://www.cnblogs.com/zhouzhendong/p/8125944.html
题目传送门 - BZOJ1823
题意概括
有n道菜，分别可以做成满式和汉式（每道菜只能做成一种形式），有m个专家。
每个专家喜欢两种菜，比如汉式猪肉和满式牛肉。
问是否存在方案使得所有专家都被满足。
题解
2-sat模版题，连方案都不用输出，水过……
代码
#include <cstring>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cmath>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;}
BZOJ1823 [JSOI2010]满汉全席 2-sat
原文地址：https://www.cnblogs.com/zhouzhendong/p/8125944.html