POJ 3678 Katu Puzzle

POJ_3678

这是一个2-SAT的问题，很容易能够看出核心变量就是x[i]，剩下的工作就是依c的值以及符号分析清楚各个x[i]之间的制约关系。

#include<stdio.h>
#include<string.h>
#define MAXD 2010
#define MAXM 4000010
int first[MAXD], next[MAXM], v[MAXM], e, N, M;
int dfn[MAXD], low[MAXD], cnt, ins[MAXD], s[MAXD], top;
int color[MAXD], col;
char oper[][5]={"AND", "OR", "XOR"};
int search(char *str)
{
int i;
for(i = 0; strcmp(str, oper[i]) != 0; i ++);
return i;
}
void add_path(int i, int j)
{
    v[e] = j;
    next[e] = first[i];
    first[i] = e;
    e ++;
}
void buid(i, j, c, op)
{
if(c)
    {
if(op == 0)
        {
            add_path(2 * i, 2 * i + 1);
            add_path(2 * j, 2 * j + 1);
        }
else if(op == 1)
        {
            add_path(2 * i, 2 * j + 1);
            add_path(2 * j, 2 * i + 1);
        }
else if(op == 2)
        {
            add_path(2 * i, 2 * j + 1);
            add_path(2 * i + 1, 2 * j);
            add_path(2 * j, 2 * i + 1);
            add_path(2 * j + 1, 2 * i);
        }
    }
else if(!c)
    {
if(op == 0)
        {
            add_path(2 * i + 1, 2 * j);
            add_path(2 * j + 1, 2 * i);
        }
else if(op == 1)
        {
            add_path(2 * i + 1, 2 * i);
            add_path(2 * j + 1, 2 * j);
        }
else if(op == 2)
        {
            add_path(2 * i, 2 * j);
            add_path(2 * i + 1, 2 * j + 1);
            add_path(2 * j, 2 * i);
            add_path(2 * j + 1, 2 * i + 1);
        }
    }
}
void init()
{
int i, j, a, b, c, op;
char str[5];
    e = 0;
    memset(first, -1, sizeof(first));
for(i = 0; i < M; i ++)
    {
        scanf("%d%d%d%s", &a, &b, &c, str);
        op = search(str);
        buid(a, b, c, op);
    }
}
void tarjan(int u)
{
int i;
    dfn[u] = low[u] = ++ cnt;
for(i = first[u]; i != - 1; i = next[i])
    {
if(!dfn[v[i]])
        {
            s[top ++] = v[i];
            ins[v[i]] = 1;
            tarjan(v[i]);
if(low[v[i]] < low[u])
                low[u] = low[v[i]];
        }
else if(ins[v[i]] && dfn[v[i]] < low[u])
            low[u] = dfn[v[i]];
    }
if(low[u] == dfn[u])
    {
for(s[top] = -1; s[top] != u;)
        {
            top --;
            ins[s[top]] = 0;
            color[s[top]] = col;
        }
        col ++;
    }
}
int com()
{
int i;
    cnt = top = col = 0;
    memset(dfn, 0, sizeof(dfn));
    memset(ins, 0, sizeof(ins));
for(i = 0; i < 2 * N; i ++)
if(!dfn[i])
        {
            s[top ++] = i;
            ins[i] = 1;
            tarjan(i);
        }
for(i = 0; i < 2 * N; i ++)
if(color[i] == color[i ^ 1])
return 0;
return 1;
}
int main()
{
while(scanf("%d%d", &N, &M) == 2)
    {
        init();
if(com())
            printf("YES\n");
else
            printf("NO\n");
    }
return 0;    
}