[POJ 3678]2-SAT判定

【题目大意】给定N个布尔型常量以及他们的一些运算结果,给出的运算包括and、xor、or,问能否找到一组常量的值使得它们满足这些约束?

【算法分析】2-SAT判定法。设i为false,i’为true
则对于约束这样连有向边(边[A,B]的意思是选了A,就必须选B):
i and j=1————–>add(i,i’)   add(j,j’)
i and j=0————–>add(i’,j)   add(j’,i)
i or j=1—————->add(i,j’)   add(j’,i)
i or j=0—————->add(i’,i)   add(j’,j)
i xor j=1—————>add(i’,j)   add(j’,i)  add(i,j’)  add(j,i’)
i xor j=0—————>add(i,j)    add(i’,j’) add(j,i)    add(j’,i’)
然后用对于强连通缩点,如果i和i’在同一强连通分量,那么无解。(意思是选了i又必须选i‘,选了i’也必须选i)

【其它】2WA,因为C++的字符串读入是从0开始的,ORZ。。。思想还停留在用pascal的时候。。。悲剧。。。
6398008 edward2 3678 Accepted 1432K 438MS G++ 2290B 2010-02-01 21:07:17

【CODE】
#include #include #include struct edge{int y;edge *next;};
int f[2000],dep[2000],color[2000],n,m,e;
edge *ls[2000];

inline void add(int x,int y){
edge *p=new edge;
p->y=y; p->next=ls[x]; ls[x]=p;
}

// i means i (a[i]=0)
// i+n means i’ (a[i]=1)
void init(){
char op[1000];
scanf("%d %dn",&n,&m);
for (int i=0;i for (int i=1;i<=m;i++){
int x,y,ans;
scanf("%d %d %d %sn",&x,&y,&ans,&op);
if (op[0]==’A’){
if (ans){
add(x,x+n);
add(y,y+n);
// add(x+n,y+n); add(y+n,x+n); /*need?*/
}
else{
add(x+n,y);
add(y+n,x);
}
}
if (op[0]==’O’){
if (ans){
add(x,y+n);
add(y,x+n);
}
else{
add(x+n,x);
add(y+n,y);
// add(x,y); add(y,x); /*need?*/
}
}
if (op[0]==’X’){
if (ans){
add(x,y+n);
add(x+n,y);
add(y,x+n);
add(y+n,x);
}
else{
add(x,y);
add(y,x);
add(x+n,y+n);
add(y+n,x+n);
}
}
}
}

int gf(int k){
if (f[k]==k) return k;
f[k]=gf(f[k]);
return f[k];
}

void dfs(int k){
for (edge *t=ls[k];t;t=t->next)
if (dep[t->y]==0){
dep[t->y]=dep[k]+1;
dfs(t->y);
if (dep[gf(t->y)] }
else if (color[gf(t->y)]==0 && dep[gf(t->y)] f[k]=f[t->y];
color[k]=1;
}

void tarjan(){
for (int i=0;i for (int i=0;i if (dep[i]==0){
dep[i]=1;
dfs(i);
}
for (int i=0;i}

bool print(){
for (int i=0;i if (f[i]==f[i+n]) return false;
return true;
}

int main(){
init();
tarjan();
if (print()) printf("YESn");
else printf("NOn");
return 0;
}

加入对话

3条评论

留下评论

您的电子邮箱地址不会被公开。