[BZOJ1823][JSOI2010]满汉全席（2-SAT）

=== ===

这里放传送门

=== ===

题解

可以发现每种食材要么选m要么选h，并且因为每个评委的要求必须至少满足一个，那么就会出现一些例如食材A选了m，食材B就必须选h这样的限制。那么这就是一个2-SAT可行性判断问题。

代码

#include<cstdio> #include<cstring> #include<algorithm> #define clear(x)(memset(x,0,sizeof(x))) using namespace std; int T,n,m,p[210],a[2010],nxt[2010],low[210],w[210],st[210],top,pos[210],tot,cnt; bool ext[210],flag; int rev(int x){return (x<=n)?x+n:x-n;} int get(){ char c=getchar(); int x=0,dlt; while (c!='m'&&c!='h') c=getchar(); dlt=(c=='m')?0:n; c=getchar(); while (c<'0'||c>'9') c=getchar(); while (c>='0'&&c<='9'){ x=x*10+c-'0';c=getchar(); } return x+dlt; } void add(int x,int y){ tot++;a[tot]=y;nxt[tot]=p[x];p[x]=tot; } void Tarjan(int u){ low[u]=w[u]=++tot; st[++top]=u;ext[u]=true; for (int i=p[u];i!=0;i=nxt[i]) if (w[a[i]]==0){ Tarjan(a[i]); low[u]=min(low[u],low[a[i]]); }else if (ext[a[i]]==true) low[u]=min(low[u],w[a[i]]); if (low[u]==w[u]){ int v;++cnt; do{ v=st[top--];pos[v]=cnt;ext[v]=false; }while (v!=u); } } int main() { scanf("%d",&T); for (int wer=1;wer<=T;wer++){ clear(p);clear(w);clear(low); clear(ext);tot=cnt=top=flag=0; scanf("%d%d",&n,&m); for (int i=1;i<=m;i++){ int v1=get(),v2=get(); add(rev(v1),v2); add(rev(v2),v1); } for (int i=1;i<=2*n;i++) if (w[i]==0) Tarjan(i); for (int i=1;i<=n;i++) if (pos[i]==pos[rev(i)]){ flag=true;break; } if (flag==true) printf("BAD\n"); else printf("GOOD\n"); } return 0; }