poj 六道2-sat第二题：

题目描述：

一些点，点的取值可以是0或者1，没有告诉你具体取值。

一些边，有权值，有运算方式（并，或，异或），要求和这条边相连的两个点经过边上的运算后的结果是边的权值。

问你有没有可能把每个点赋值满足所有边的要求。

解题报告：

每个点只有0，1两种值，并且和边对面的点有约束条件，所以可以转化为2-sat问题。

令i表示点i去0，i + n表示点i取1.

点i与点j and 等于0时。 i + n -> j, j + n -> i

and 等于 1时，要求i和j必须为1，不能为0.

不能为0的处理时：如果i取0，那么i就要取1.

即：i -> i + n。

剩下的就是类似的方法了，具体见代码。

代码如下：

#include<iostream>
using namespace std;
#define size 2100
int v[size], cnt;
struct edge{int to, next;}e[3000000];
void insert(int from, int to)
{
    e[cnt].to = to; e[cnt].next = v[from]; v[from] = cnt++;
}
int index, dfn[size], low[size], instack[size], sta[size], top;
int belong[size], cntnum;
void tarjan(int id)
{
    dfn[id] = low[id] = ++index;
    instack[id] = 1; sta[top++] = id;
    int tmp = v[id];
    while(tmp != -1)
    {
        if (!dfn[e[tmp].to])
        {
            tarjan(e[tmp].to);
            if (low[e[tmp].to] < low[id]) low[id] = low[e[tmp].to];
        }
        else if (instack[e[tmp].to] && dfn[e[tmp].to] < low[id])
            low[id] = dfn[e[tmp].to];
        tmp = e[tmp].next;
    }
    if (dfn[id] == low[id])
    {
        do
        {
            tmp = sta[--top]; instack[tmp] = 0;
            belong[tmp] = cntnum;
        }while(tmp != id);
        cntnum++;
    }
}
int n, m, a, b, c;
char str[7];
int main()
{
    scanf("%d%d", &n, &m);
    cnt = 0;
    memset(v, -1, sizeof(v));
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d%d%s", &a, &b, &c, str);
        if (strcmp(str, "AND") == 0)
        {
            if (c == 1)
            {
                insert(a + n, b + n);
                insert(b + n, a + n);
                insert(a, a + n);
                insert(b, b + n);
            }
            else
            {
                insert(a + n, b);
                insert(b + n, a);
            }
        }
        else if (strcmp(str, "OR") == 0)
        {
            if (c == 1)
            {
                insert(a, b + n);
                insert(b, a + n);
            }
            else
            {
                insert(a, b);
                insert(b, a);
                insert(a + n, a);
                insert(b + n, b);
            }
        }
        else
        {
            if (c == 1)
            {
                insert(a, b + n);
                insert(a + n, b);
                insert(b, a + n);
                insert(b + n, a);
            }
            else
            {
                insert(a, b);
                insert(a + n, b + n);
                insert(b, a);
                insert(b + n, a + n);
            }
        }
    }
    index = cntnum = top = 0;
    memset(dfn, 0, sizeof(dfn));
    for(int i = 0; i < 2 * n; i++)
        if (!dfn[i]) tarjan(i);
    bool flag = true;
    for(int i = 0; i < n; i++)
        if (belong[i] == belong[i + n])
        {
            flag = false;
            break;
        }
    if (flag) printf("YES\n");
    else printf("NO\n");
    return 0;
}