POJ 3678 Katu Puzzle 2-sat 判断是不是有合法解

POJ 3678 Katu Puzzle 2-sat 判断是否有合法解

建图如下

AND 1 a0->a1,b0->b1
AND 0 a1->b0,b1->a0
OR 1 a0->b1,b0->a1
OR 0 a1->a0,b1->b0
XOR 1 a0->b1,a1->b0,b1->a0,b0->a1
XOR 0 a0->b0,b0->a0,a1->b1,b1->a1

需要注意的是，如果a,b的值已经确定，比如说and 1 操作的时候，a,b的值都只能是1，那么需要加 a0->a1,b0->b1，这种加边跟平常的加边情况不同，具体请看 http://blog.sina.com.cn/s/blog_68629c7701010gf1.html

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define MAXN 10005
#define MAXM 4000005
#define INF 1000000000
using namespace std;
struct Edge
{
    int v, next;
}edge[MAXM];
int n, m, e, head[MAXN];
int scc, index, fa[MAXN];
int instack[MAXN], low[MAXN], dfn[MAXN];
int st[MAXN], top;
void init()
{
    e = scc = index = top = 0;
    memset(head, -1, sizeof(head));
    memset(instack, 0, sizeof(instack));
    memset(dfn, 0, sizeof(dfn));
}
void insert(int x, int y)
{
    edge[e].v = y;
    edge[e].next = head[x];
    head[x] = e++;
}
void tarjan(int u)
{
    int v;
    dfn[u] = low[u] = ++index;
    st[++top] = u;
    instack[u] = 1;
    for(int i = head[u]; i != -1; i = edge[i].next)
    {
        v = edge[i].v;
        if(!dfn[v])
        {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(instack[v]) low[u] = min(low[u], dfn[v]);
    }
    if(dfn[u] == low[u])
    {
        scc++;
        do
        {
            v = st[top--];
            instack[v] = 0;
            fa[v] = scc;
        }while(v != u);
    }
}
void build()
{
    char s[15];
    int x, y, w;
    while(m--)
    {
        scanf("%d%d%d%s", &x, &y, &w, s);
        x++; y++;
        if(s[0] == 'A')
        {
            if(w == 0)
            {
                insert(x + n, y);
                insert(y + n, x);
            }
            else
            {
                insert(x, x + n);
                insert(y, y + n);
            }
        }
        else if(s[0] == 'O')
        {
            if(w == 0)
            {
                insert(x + n, x);
                insert(y + n, y);
            }
            else
            {
                insert(x, y + n);
                insert(y, x + n);
            }
        }
        else
        {
            if(w == 0)
            {
                insert(x + n, y + n);
                insert(x, y);
                insert(y, x);
                insert(y + n, x + n);
            }
            else
            {
                insert(x, y + n);
                insert(y, x + n);
                insert(y + n, x);
                insert(x + n, y);
            }
        }
    }
}
bool check()
{
    for(int i = 1; i <= n; i++)
        if(fa[i] == fa[i + n]) return false;
    return true;
}
void solve()
{
    for(int i = 1; i <= 2 * n; i++)
        if(!dfn[i]) tarjan(i);
    if(check()) printf("YES\n");
    else printf("NO\n");
}
int main()
{
    while(scanf("%d%d", &n, &m) != EOF)
    {
        init();
        build();
        solve();
    }
    return 0;
}

POJ 3678 Katu Puzzle 2-sat 判断是不是有合法解

相关推荐