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 Vi a value Xi (0 ≤ Xi ≤ 1) such that for each edge e(a, b) labeled by op and c, the following formula holds:Xa op Xb = cThe 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

X0 = 1, X1 = 1, X2 = 0, X3 = 1.

?

Source

POJ Founder Monthly Contest – 2008.07.27, Dagger

胡亂地搞，竟然就AC了

借用別人的解題報告

思路：因為給出結點 a ，b，值 c，還有判斷方式OP，這種一看當然就知道是用2SAT做了。為什么說是深刻理解2SAT呢，因為……2SAT中說過，只有關系確定的才能連邊，否則不能連邊；還有一個重要的是，如果某個條件必須為某個值時，自身與自身的相反條件也要連邊，具體看下面解釋：

現在設 2*a為1，2*a+1為0；當然 2*b為1，2*b+1為0：

1.當OP為’And‘時：

（1）當c=1時，那么只有a 與 b同時為1時，a ?AND b才等于1，并且有且只有當a與b都為1時這個條件才成立，所以a與b一定要等1，所以連邊<2*a+1,2*a>，<2*b+1,2*b>，表示不管怎么樣，a與b的情況都等于1，即：當a等于0時a必等于1，b等于0時b必等于1，這個剛開始我看別人的解題報告就是這么說的，然后自己也沒太理解，其實真正的內涵就是強制執行a與b都等于1 ！（如果a等于1了的話當然這條邊就沒用了，如果a等于0的話，那么這條連就可以起到把a強制等于1以符合題目條件情況了，就是如此簡單，得慢慢理解）

（2）當c=0時，那么當a等于0時，b可能為0也可以為1，所以是不確定關系，由上面說的一定是確定關系才能連邊，所以a為0的情況就不能連邊了；當a等于1時，b一定為0才能使 a AND b =0，所以連邊：<2*a,2*b+1>，當然還有<2*b,2*a,+1>。

2.當OP為OR時，

（1）當c=1時，那么當a=1時，b=1或者b=0，所以當a=1時出現了兩種關系，就是不確定了，就不用連邊了；當a=0時，那么b一定=1,所以是確定關系，連邊：<2*a+1,2*b>，當然還有<2*b+1,2*a>。

（2）當c=0時，那么只有當a=b=0這個關系，所以這個和上面1（1）情況就一樣了，上面是強制執行a=b=1的情況，而這里因為只有a=b=0的情況，所以也要強制執行a=b=0,即連邊：<2*a,2*a+1>,<2*b,2*b+1>。

3.當OP為XOR時，因為如果a=1,那么b必=0；a=0，b必=1；b=1，a必=0；b=0，a必=1。如此看，這四個關系都是確定的，所以都要連邊，但是其實我們可以不連，一條邊都不用連，因為出a=1的時候一定不會再出現a=0了，這四條邊是不會產生矛盾的，所以強連通縮點后不會出現belong[2*a]=belong[2*a+1]的情況的，所以連了也沒用，只是多加了點判斷的時間罷了……這在別人的解題報告里說的是形成了組環了，都是一個意思。比如：a=1,b=0與b=0,a=1在tarjan中會形成一個新的結點，也就是自環，所以……在異或這種情況中只能選擇a=0或者a=1，所以不會出現矛盾……故不用連邊了！

#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<bitset>
#include<map>
#include<vector>
#include<stdlib.h>
#include <stack>
using namespace std;
#define PI acos(-1.0)
#define max(a,b) (a) > (b) ? (a) : (b)  
#define min(a,b) (a) < (b) ? (a) : (b)
#define ll long long
#define eps 1e-10
#define MOD 1000000007
#define N 1006
#define inf 1e12
int n,m;
vector<int> e[N];

int tot;
int head[N];
int vis[N];
int tt;
int scc;
stack<int>s;
int dfn[N],low[N];
int col[N];
struct Node
{
    int from;
    int to;
    int next;
}edge[N*N];
void init()
{
    tot=0;
    scc=0;
    tt=0;
    memset(head,-1,sizeof(head));
    memset(dfn,-1,sizeof(dfn));
    memset(low,0,sizeof(low));
    memset(vis,0,sizeof(vis));
    memset(col,0,sizeof(col));
}
void add(int s,int u)//鄰接矩陣函數
{
    edge[tot].from=s;
    edge[tot].to=u;
    edge[tot].next=head[s];
    head[s]=tot++;
}
void tarjan(int u)//tarjan算法找出圖中的所有強連通分支
{
    dfn[u] = low[u]= ++tt;
    vis[u]=1;
    s.push(u);
    int cnt=0;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].to;
        if(dfn[v]==-1)
        {
        //    sum++;
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v]==1)
          low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u])
    {
        int x;
        scc++;
        do{
            x=s.top();
            s.pop();
            col[x]=scc;
            vis[x]=0;
        }while(x!=u);
    }
}
bool two_sat(){
    
    for(int i=0;i<2*n;i++){
        if(dfn[i]==-1){
            tarjan(i);
        }
    }
    for(int i=0;i<n;i++){
        if(col[2*i]==col[2*i+1]){
            return false;
        }
    }
    return true;
}
int main()
{
    while(scanf("%d%d",&n,&m)==2){
         init();
         for(int i=0;i<N;i++) e[i].clear();
         while(!s.empty()){
             s.pop();
         }
        int a,b,c;
        char s[6];
        for(int i=0;i<m;i++){
            scanf("%d%d%d%s",&a,&b,&c,s);
            if(s[0]=='A'){
                if(c==1){
                    //e[2*a+1].push_back(2*a);
                    //e[2*b+1].push_back(2*b);
                    add(2*a+1,2*a);
                    add(2*b+1,2*b);
                }
                else{
                    //e[2*a].push_back(2*b+1);
                    //e[2*b].push_back(2*a+1);
                    add(2*a,2*b+1);
                    add(2*b,2*a+1);
                }
            }
            else if(s[0]=='O'){
                if(c==1){
                    //e[2*a+1].push_back(2*b);
                    //e[2*b+1].push_back(2*a);
                    add(2*a+1,2*b);
                    add(2*b+1,2*a);
                }
                else{
                    //e[2*a].push_back(2*a+1);
                    //e[2*b].push_back(2*b+1);
                    add(2*a,2*a+1);
                    add(2*b,2*b+1);
                }
            }
        }
        if(two_sat()){
            printf("YES\n");
        }
        else{
            printf("NO\n");
        }
    }
    return 0;
}

?