题意：给出a, b, c 和操作类型 （与或异或），问是否满足所有的式子
主要是建图：
对于 and ， c == 1: 说明 a 和 b都是1，那么 0 就不能取， a' -> a , b' - > b ，因为 a 和 a'是对立事件，对于 a' - >a说明，a'如果成立，那么a也一定存在，显然这是不可能的所以a'不会 成立的。 c == 0 说明 a 和 b不全为1, a' -> b , b' -> a
对于 or, c == 1 ：说明 a 和 b 不全为 0 , a' -> b, b' -> a c == 0 时 ：说明 a 和 b 同时为0， a -> a' , b -> b‘ // a成立时候，a'可能不成立，所以a不会成立
对于xor， c == 1：说明 a 和 b不相等 ， a -> b' , b -> a' , a' -> b, b' - >a // a b不相等有两张情况， a == 0 || b == 0 ; a == 1 || b == 1, 每一种建立两条边
c == 0：说明 a 和 b 相等， a' -> b', b' -> a' , a - > b, b -> a // a b相等有两种情况： a == b == 0, 或者 a == b == 1; 为什么不把前面ab同时为0 和 ab同时为1的情况合并呢， 合并肯定不对啊， a' -> a ， a -> a'，b- >b', b' - >b 什么啊这是=_=...
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int Maxn = * + ;
const int Maxm = * +;
struct Edge
{
int to, Next;
}edge[Maxm];
int head[Maxn], tot;
void init()
{
tot = ;
memset(head, -, sizeof(head));
}
void addedge(int u, int v)
{
edge[tot].to = v;
edge[tot].Next = head[u];
head[u] = tot++;
}
int low[Maxn], dfn[Maxn], Stack[Maxn], belong[Maxn];
int Index, top;
int scc;
bool Instack[Maxn];
void Tarjan(int u)
{
int v;
low[u] = dfn[u] = ++Index;
Stack[top++] = u;
Instack[u] = true;
for (int i = head[u]; i != -; i = edge[i].Next)
{
v = edge[i].to;
if (!dfn[v])
{
Tarjan(v);
if (low[u] > low[v])
low[u] = low[v];
}
else if (Instack[v] && low[u] > dfn[v])
low[u] = dfn[v];
}
if (low[u] == dfn[u])
{
scc++;
do
{
v = Stack[--top];
Instack[v] = false;
belong[v] = scc;
} while (u != v);
}
}
bool solvable(int n)
{
memset(dfn, , sizeof(dfn));
memset(low, , sizeof(low));
memset(belong, , sizeof(belong));
memset(Instack, false, sizeof(Instack));
Index = top = scc = ;
for (int i = ; i < n; i++)
{
if (!dfn[i])
Tarjan(i);
}
for (int i = ; i < n; i += )
{
if (belong[i] == belong[i ^ ] )
return false;
}
return true;
}
int main()
{
int n, m;
while (scanf("%d%d", &n, &m) != EOF)
{
init();
int a, b, c;
char op[];
while (m--)
{
scanf("%d%d%d%s", &a, &b, &c, op);
a = a * ; //这里要乘以2
b = b * ;
if (strcmp(op, "AND") == )
{
if (c)
{
addedge(a, a ^ );
addedge(b, b ^ );
}
else
{
addedge(a ^ , b);
addedge(b ^ , a);
}
}
else if (strcmp(op, "OR") == )
{
if (c)
{
addedge(a, b ^ );
addedge(b, a ^ );
}
else
{
addedge(a ^ , a);
addedge(b ^ , b);
}
}
else if (strcmp(op, "XOR") == )
{
if (c)
{
addedge(a, b ^ );
addedge(b, a ^ );
addedge(a ^ , b);
addedge(b ^ , a);
}
else
{
addedge(a, b);
addedge(b, a);
addedge(a ^ , b ^ );
addedge(b ^ , a ^ );
}
}
} if( solvable(n * ) )
printf("YES\n");
else
printf("NO\n"); }
return ;
}