poj3678 Katu Puzzle

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 = 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

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

POJ Founder Monthly Contest – 2008.07.27, Dagger
点数的数据范围是不是有问题..当然很大可能是我太菜了
考虑一般性建图 那么发现建图都是普通的建图只有当or的时候有一个问题 那么就是只有当我上下都是0的时候我才能出答案 这我就从1向0连一条边 表示如果这个点我需要是1 那么他一定会变成0 这样如果出现1 那么显然在缩点的时候答案会变成不合法 结束..

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
    return x*f;
}
const int M=1000010;
const int N=10000; 
struct node{
    int y,next;
}data[4*N];
int h[N],num,dfn[N],low[N],stackf[N],q[N],top,s,b[N],n,m,id[N][2];
inline void insert1(int x,int y){
    data[++num].y=y;data[num].next=h[x];h[x]=num;
}
inline void tarjan(int x){
    dfn[x]=low[x]=++num;stackf[x]=1;q[++top]=x;
    for (int i=h[x];i;i=data[i].next){
        int y=data[i].y;
        if(!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);else if (stackf[y]) low[x]=min(low[x],dfn[y]);
    }
    if (dfn[x]==low[x]){
        int y;++s;
        do{y=q[top--];stackf[y]=0;b[y]=s;}while(y!=x);
    }
}
int main(){
    freopen("poj3678.in","r",stdin);
    n=read();m=read();
    for (int i=0;i<n;++i) id[i][0]=i<<1,id[i][1]=i<<1|1;
    for (int i=1;i<=m;++i){static int x,y,c;static char s[10];
        x=read();y=read();c=read();scanf("%s",s+1);
        if(s[1]=='A'){
            if(c) insert1(id[x][0],id[x][1]),insert1(id[y][0],id[y][1]);
            else insert1(id[x][1],id[y][0]),insert1(id[y][1],id[x][0]);
        }
        if (s[1]=='O'){
            if (c)insert1(id[x][0],id[y][1]),insert1(id[y][0],id[x][1]);
            else insert1(id[x][1],id[x][0]),insert1(id[y][1],id[y][0]);
        }
        if (s[1]=='X'){
            if (c){
                insert1(id[x][0],id[y][1]),insert1(id[y][0],id[x][1]);
                insert1(id[x][1],id[y][0]),insert1(id[y][1],id[x][0]);
            }else{
                insert1(id[x][0],id[y][0]),insert1(id[y][0],id[x][0]);
                insert1(id[x][1],id[y][1]),insert1(id[y][1],id[x][1]);
            }
        }
    }num=0;
    for (int i=0;i<n<<1;++i) if (!dfn[i]) tarjan(i);
    for (int i=0;i<n;++i) if (b[id[i][0]]==b[id[i][1]]) {puts("NO");return 0;}
    puts("YES");
    return 0;
}