【题目大意】给定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
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
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)]
color[k]=1;
}
void tarjan(){
for (int i=0;i
dep[i]=1;
dfs(i);
}
for (int i=0;i
bool print(){
for (int i=0;i
return true;
}
int main(){
init();
tarjan();
if (print()) printf("YESn");
else printf("NOn");
return 0;
}
