题意：给定相关运算结果，问是否存在这样的值满足条件。
思路：对与A，要么A是1，要么A是0，这样就是一个2-sat问题了。
这题主要难点在于建边，2-sat部分并不难。
一开始too young了，没把边建对。
讲下建边吧：
这里我们在图中用A代表A=1，用A‘代表A=0。
A AND B =1，这种情况A和B都要为1，那么A’必然无解，可以A'→A，B'→B。
A AND B =0，AB不同时为1，那么A→B‘，B→A’。
A OR B =1，A为0则B一定为1，A‘→B，B’→A。
A OR B =0，AB一定都为0，A→A‘，B→B’。
A XOR B =1，AB不相同，A→B’，B→A'，A'→B，B‘→A。
A XOR B =0，AB相同，A→B，B→A，A’→B‘，B’→A‘。
建完之后判断就行了。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int fst[3000],next[5000000],node[5000000],en;
int n,m,a,b,c,ans,cnt,s[3000];
bool v[3000];
char str[5];
void add(int x,int y)
{
next[++en]=fst[x];
fst[x]=en;
node[en]=y;
}
bool dfs(int x)
{
if(v[x^1])return false;
if(v[x])return true;
v[x]=1;
s[cnt++]=x;
for(int i=fst[x]; i!=-1; i=next[i])
{
if(!dfs(node[i]))return false;
}
return true;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
en=0;
memset(fst,-1,sizeof(fst));
for(int i=0; i<m; i++)
{
scanf("%d%d%d%s",&a,&b,&c,str);
if(str[0]=='A')
{
if(c==1)
{
add(2*a+1,2*a);
add(2*b+1,2*b);
}
else if(c==0)
{
add(2*a,2*b+1);
add(2*b,2*a+1);
}
}
else if(str[0]=='O')
{
if(c==0)
{
add(2*a,2*a+1);
add(2*b,2*b+1);
}
if(c==1)
{
add(2*a+1,2*b);
add(2*b+1,2*a);
}
}
else if(str[0]=='X')
{
if(c==1)
{
add(2*a,2*b+1);
add(2*b+1,2*a);
add(2*a+1,2*b);
add(2*b,2*a+1);
}
else if(c==0)
{
add(2*a,2*b);
add(2*b,2*a);
add(2*a+1,2*b+1);
add(2*b+1,2*a+1);
}
}
}
memset(v,0,sizeof(v));
ans=0;
for(int i=0; i<n; i++)
{
if(!v[2*i]&&!v[2*i+1])
{
cnt=0;
if(!dfs(2*i))
{
while(cnt>0)v[s[--cnt]]=0;
if(!dfs(2*i+1))
{
ans=1;
break;
}
}
}
}
if(ans)cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}