[JSOI2010 满汉全席]2-sat

【题目链接】http://61.187.179.132:8080/JudgeOnline/showproblem?problem_id=1823
【算法分析】
对于每种材料，有做成满式和汉式两种情况，然后两者取且必须取一种。
而且约束条件是，(A做成XX式 or B做成yy式) = true。
逻辑运算符。。。很容易想到2-sat。
回想2-sat的建图，一条边(A，B)的意义是：如果你选了A，那么就必须选B。
恩，这个题目的逻辑式子转化成：加入你选了A的对立面，那么一定要选B啊。
恩，就这样。。。
【其它】很久没2-sat了，1Y。
【CODE】
#include #include #include const int N=1000;
const int E=1000000;
int n,m,e,times,ct,tot;
int lx[N],ly[N];
int fa[N],order[N];
bool v[N],Type;

struct Graph_t{
struct edge{int x,y;edge *next;}g[E],*ls[N];
void clr(){e=0; memset(ls,0,sizeof(ls));}
void addedge(int x,int y){
g[++e].x=x; g[e].y=y; g[e].next=ls[x]; ls[x]=&g[e];
}

void op(){
int tmp=e;
clr();
for (int i=1;i<=tmp;i++) addedge(g[i].y,g[i].x);
}

void dfs(int p){
v[p]=true;
for (edge *t=ls[p];t;t=t->next)
if (!v[t->y]) dfs(t->y);
if (Type) fa[p]=ct;
else order[++tot]=p;
}
}G;

int Get(){
char ch[20];
int x;
scanf("%s",ch);
sscanf(ch+1,"%d",&x);
if (ch[0]==’h’) x+=n;
return x;
}

void init(){
int i;
scanf("%d%d",&n,&m);
for (i=1;i<=m;i++){
lx[i]=Get();
ly[i]=Get();
}
}

void build(){
G.clr();
int i,j;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++){
if (lx[j]==i+n) G.addedge(i,ly[j]);
if (ly[j]==i+n) G.addedge(i,lx[j]);
}
for (i=n+1;i<=n*2;i++)
for (j=1;j<=m;j++){
if (lx[j]==i-n) G.addedge(i,ly[j]);
if (ly[j]==i-n) G.addedge(i,lx[j]);
}
}

void SCC(){
memset(v,false,sizeof(v));
tot=0;
Type=false;
for (int i=1;i<=2*n;i++)
if (!v[i]) G.dfs(i);
Type=true;
G.op();
memset(v,false,sizeof(v));
for (int i=tot;i>=1;i–)
if (!v[order[i]]){
ct=order[i];
G.dfs(order[i]);
}
}

void output(){
bool ans=true;
for (int i=1;i<=n;i++)
if (fa[i]==fa[i+n]) ans=false;
if (ans) puts("GOOD");
else puts("BAD");
}

int main(){
int Tc,i;
scanf("%d",&Tc);
for (i=1;i<=Tc;i++){
init();
build();
SCC();
output();
}
}