POJ 3678 Katu Puzzle（2 - SAT）

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_i a 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

Hint

X₀ = 1, X₁ = 1, X₂ = 0, X₃ = 1.

题目大意：有 n 个变量和m个条件，每个条件格式如下：

给你三个数a ， b ， c 和一个运算字符串op (AND , OR , XOR 等)，要求Xa op Xb = c 。

问：是否能给每个变量赋值（0 或 1），使得每个条件都能满足？

解题思路：这道题是一道2 - SAT问题的变形，2 - SAT 问题中是通过条件建立图中的边，这道题也类似，也是也要通过条件建立相应的边，只不过有些细节需要注意。

请看代码：

#include<iostream>

#include<cstring>

#include<string>

#include<algorithm>

#include<vector>

#include<cmath>

#include<cstdio>

#include<queue>

#define mem(a , b) memset(a , b , sizeof(a))

using namespace std ;

const int MAXN = 10000 ;

vector<int> G[MAXN * 2] ;

bool mark[MAXN * 2] ;

int S[MAXN] , c ;  // 模拟栈

char op[8] ;

int n , m ;

int pan ;  // 判断标志

void chu()

{

    int i ;

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

        G[i].clear() ;

    mem(mark , 0) ;

}

void init()

{

    chu() ;

    pan = 0 ;

    int i ;

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

    {

        int a , b , c ;

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

        scanf("%s" , op) ;

        if(op[0] == 'A')

        {

            if(c == 1)  // 注意此时建边的方式

            {

                G[2 * a].push_back(2 * a + 1) ;

                G[2 * b].push_back(2 * b + 1) ;

            }

            else

            {

                G[2 * a + 1].push_back(2 * b) ;

                G[2 * b + 1].push_back(2 * a) ;

            }

        }

        else if(op[0] == 'X')

        {

            if(c == 0)

            {

                G[2 * a].push_back(2 * b) ;

                G[2 * a + 1].push_back(2 * b + 1) ;

                G[2 * b].push_back(2 * a) ;

                G[2 * b + 1].push_back(2 * a + 1) ;

            }

            else

            {

                G[2 * a].push_back(2 * b + 1) ;

                G[2 * a + 1].push_back(2 * b) ;

                G[2 * b].push_back(2 * a + 1) ;

                G[2 * b + 1].push_back(2 * a) ;

            }

        }

        else

        {

            if(c == 0) // 注意此时建边的方式

            {

                G[2 * a + 1].push_back(2 * a) ;

                G[2 * b + 1].push_back(2 * b) ;

            }

            else

            {

                G[2 * a].push_back(2 * b + 1) ;

                G[2 * b].push_back(2 * a + 1) ;

            }

        }

    }

}

bool dfs(int x)

{

    if(mark[x ^ 1]) return false ;

    if(mark[x]) return true ;

    mark[x] = true ;

    S[c ++] = x ;

    int i ;

    for(i = 0 ; i < G[x].size() ; i ++)

    {

        if(!dfs(G[x][i]))

            return false ;

    }

    return true ;

}

void solve()

{

    if(pan)

        puts("NO") ;

    else

    {

        int i ;

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

        {

            if(!mark[i * 2] && !mark[i * 2 + 1])

            {

                c = 0 ;

                if(!dfs(i * 2))

                {

                    while (c > 0)

                    {

                        mark[ S[-- c] ] = false ;

                    }

                    if(!dfs(i * 2 + 1))

                    {

                        pan = 1 ;

                        break ;

                    }

                }

            }

        }

        if(pan)

            puts("NO") ;

        else

            puts("YES") ;

    }

}

int main()

{

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

    {

        init() ;

        solve() ;

    }

    return 0 ;

}

巴特西

POJ 3678 Katu Puzzle（2 - SAT） - from lanshui_Yang

最新文章

热门文章