BZOJ_1823_[JSOI2010]满汉全席_2-sat
题意：http://www.lydsy.com/JudgeOnline/problem.php?id=1823
分析：一道比较容易看出来的2-sat。
设满为1，汉为0；
题目要求两个至少满足一个。那么建图同奶牛议会http://www.cnblogs.com/suika/p/8457467.html。
之后求一遍强连通分量。
如果同一个点的true和false在一个强连通分量中就不可能满足。
代码：
#include <stdio.h>#include <string.h>#include <algorithm>using namespace std;#define N 250#define M 4500int head[N],to[M],nxt[M],cnt,n,m,ins[N];char s1[20],s2[20];int tot,dfn[N],low[N],st[N],top,bel[N],scc;inline void add(int u,int v){ ???to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;}void tarjan(int x){ ???dfn[x]=low[x]=++tot; ???st[top++]=x;ins[x]=1; ???for(int i=head[x];i;i=nxt[i]){ ???????if(!dfn[to[i]]){ ???????????tarjan(to[i]); ???????????low[x]=min(low[x],low[to[i]]); ???????}else if(ins[to[i]]){ ???????????low[x]=min(low[x],dfn[to[i]]); ???????} ???} ???if(low[x]==dfn[x]){ ???????int t=st[--top];ins[t]=0; ???????bel[t]=++scc; ???????while(t^x){ ???????????t=st[--top];ins[t]=0; ???????????bel[t]=scc; ???????} ???}}int main(){ ???int T; ???scanf("%d",&T); ???while(T--){ ???????memset(head,0,sizeof(head));cnt=0;tot=0;scc=0; ???????memset(dfn,0,sizeof(dfn)); ???????memset(low,0,sizeof(low)); ???????scanf("%d%d",&n,&m); ???????int x,y,tx,ty; ???????for(int i=1;i<=m;i++){ ???????????scanf("%s%s",s1,s2); ???????????if(s1[0]==‘m‘)tx=1;else tx=0; ???????????if(s2[0]==‘m‘)ty=1;else ty=0; ???????????sscanf(s1+1,"%d",&x); ???????????sscanf(s2+1,"%d",&y); ???????????add((1-tx)*n+x,ty*n+y); ???????????add((1-ty)*n+y,tx*n+x); ???????} ???????int flg=0; ???????for(int i=1;i<=n+n;i++)if(!dfn[i])tarjan(i); ???????for(int i=1;i<=n;i++){ ???????????if(bel[i]==bel[i+n]){ ???????????????flg=1;break; ???????????} ???????} ???????puts(flg?"BAD":"GOOD"); ???}}BZOJ_1823_[JSOI2010]满汉全席_2-sat+tarjan
原文地址：https://www.cnblogs.com/suika/p/8457491.html