2-sat（and,or,xor）poj3678

Katu Puzzle

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 7949		Accepted: 2914

Description

Katu Puzzle is presented as a directed graph G(V, E) with each edge e(a, b) labeled by a boolean operator op (one of AND, OR, XOR) and an integer c (0 ≤ c ≤ 1). One Katu is
solvable if one can find each vertex V_ia value X_i (0 ≤ X_i≤ 1) such that for each edge e(a, b) labeled by op and c, the following formula holds:

X_a op X_b = c

The calculating rules are:

AND	0	1
0	0	0
1	0	1

OR	0	1
0	0	1
1	1	1

XOR	0	1
0	0	1
1	1	0

Given a Katu Puzzle, your task is to determine whether it is solvable.

Input

The first line contains two integers N (1 ≤ N ≤ 1000) and M,(0 ≤ M ≤ 1,000,000) indicating the number of vertices and edges.

The following M lines contain three integers a (0 ≤ a < N), b(0 ≤ b < N), c and an operator op each, describing the edges.

Output

Output a line containing "YES" or "NO".

Sample Input

4 4

0 1 1 AND

1 2 1 OR

3 2 0 AND

3 0 0 XOR

Sample Output

YES


题意：给出一个连通图对于每条边都有一种操作（and，or，xor），使两个端点的操作结果是c，问是否存在这样一个连通图，存在输出YES否者输出NO
分析：裸的2-sat操作
公式：i&j=1  (i-->i+n)  (j-->j+n)
           i&j=0  (i+n-->j)  (j+n-->i)
           i|j=1   (i-->j+n)  (j-->i+n)
           i|j=0   (i+n-->i)  (j+n-->j)
          i^j=1   (i-->j+n)  (j+n-->i)  (j-->i+n)  (i+n-->j)
          i^j=0   (i-->j)  (j-->i)  (i+n-->j+n)  (j+n-->i+n)
程序;

#include"string.h"

#include"stdio.h"

#include"iostream"

#include"algorithm"

#include"queue"

#include"stack"

#include"stdlib.h"

#include"math.h"

#define inf 10000000

#define INF 0x3f3f3f3f

const double PI=acos(-1.0);

const double r2=sqrt(2.0);

const int M=1010;

const int N=1010*1000*4;

#define eps 1e-10

using namespace std;

struct node

{

    int u,v,next;

}edge[N];

stack<int>q;

int t,head[M],dfn[M],low[M],belong[M],use[M],num,index;

void init()

{

    t=0;

    memset(head,-1,sizeof(head));

}

void add(int u,int v)

{

    edge[t].u=u;

    edge[t].v=v;

    edge[t].next=head[u];

    head[u]=t++;

}

void tarjan(int u)

{

    dfn[u]=low[u]=++index;

    q.push(u);

    use[u]=1;

    for(int i=head[u];i!=-1;i=edge[i].next)

    {

        int v=edge[i].v;

        if(!dfn[v])

        {

            tarjan(v);

            low[u]=min(low[u],low[v]);

        }

        else if(use[v])

            low[u]=min(low[u],dfn[v]);

    }

    if(low[u]==dfn[u])

    {

        num++;

        int p;

        do

        {

            p=q.top();

            q.pop();

            use[p]=0;

            belong[p]=num;

        }while(p!=u);

    }

}

int slove(int n)

{

    num=index=0;

    memset(use,0,sizeof(use));

    memset(dfn,0,sizeof(dfn));

    for(int i=0;i<n*2;i++)

        if(!dfn[i])

        tarjan(i);

    for(int i=0;i<n;i++)

        if(belong[i]==belong[i+n])

        return 0;

    return 1;

}

int main()

{

    int n,m,a,b,c,i;

    char str[9];

    while(scanf("%d%d",&n,&m)!=-1)

    {

        init();

        for(i=1;i<=m;i++)

        {

            scanf("%d%d%d%s",&a,&b,&c,str);

            if(strcmp(str,"AND")==0)

            {

                if(c)

                {

                    add(a,a+n);

                    add(b,b+n);

                }

                else

                {

                    add(b+n,a);

                    add(a+n,b);

                }

            }

            else if(strcmp(str,"OR")==0)

            {

                if(c)

                {

                    add(b,a+n);

                    add(a,b+n);

                }

                else

                {

                    add(a+n,a);

                    add(b+n,b);

                }

            }

            else

            {

                if(c)

                {

                    add(a,b+n);

                    add(b,a+n);

                    add(b+n,a);

                    add(a+n,b);

                }

                else

                {

                    add(a,b);

                    add(b,a);

                    add(a+n,b+n);

                    add(b+n,a+n);

                }

            }

        }

        if(slove(n))

            printf("YES\n");

        else

            printf("NO\n");

    }

}

巴特西

2-sat（and,or,xor）poj3678

最新文章

热门文章