| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 6553 | Accepted: 2401 |
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:
|
|
|
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
Source
经典2-SAT问题
构图时，根据条件找可以确定关系的形如A->B这样的关系式
i表示i取1，~i表示i取0
i AND j =1 ~i->i, ～j->j, i->j, j->i,后面两个关系式构成一个环，i,j在同一强连通分量中，可以免去
i AND j = 0 i->~i, j->~j 而~i推不出j为0还是1
i OR j =1 ~i->j, ~j->i
i OR J =0 i->~i, j->~j, ~j->~i, ~i->~j 又有环，可以省略
i XOR j =1 i->~j, j->~i, ~i->j, ~j->i
i XOR j =0 i->j, j->i, ~i->~j, ~j->~i 又构成两个环
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int VM=2010; const int EM=4000010; const int INF=0x3f3f3f3f; struct Edge{ int to,nxt; }edge[EM<<1]; int n,m,cnt,dep,top,atype,head[VM]; int dfn[VM],low[VM],vis[VM],belong[VM]; int stack[VM]; void Init(){ cnt=0, atype=0, dep=0, top=0; memset(head,-1,sizeof(head)); memset(vis,0,sizeof(vis)); memset(low,0,sizeof(low)); memset(dfn,0,sizeof(dfn)); memset(belong,0,sizeof(belong)); } void addedge(int cu,int cv){ edge[cnt].to=cv; edge[cnt].nxt=head[cu]; head[cu]=cnt++; } void Tarjan(int u){ dfn[u]=low[u]=++dep; stack[top++]=u; vis[u]=1; for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(!dfn[v]){ Tarjan(v); low[u]=min(low[u],low[v]); }else if(vis[v]) low[u]=min(low[u],dfn[v]); } int j; if(dfn[u]==low[u]){ atype++; do{ j=stack[--top]; belong[j]=atype; vis[j]=0; }while(u!=j); } } int main(){ //freopen("input.txt","r",stdin); while(~scanf("%d%d",&n,&m)){ Init(); char op[10]; int i,j,c; while(m--){ scanf("%d%d%d%s",&i,&j,&c,op); if(op[0]=='A'){ if(c){ addedge(2*i+1,2*i); addedge(2*j+1,2*j); //addedge(2*i,2*j);//2*i和2*j在同一个环中，肯定满足 //addedge(2*j,2*i); }else{ addedge(2*i,2*j+1); addedge(2*j,2*i+1); } }else if(op[0]=='O'){ if(c){ addedge(2*i+1,2*j); addedge(2*j+1,2*i); }else{ addedge(2*i,2*i+1); addedge(2*j,2*j+1); //addedge(2*i+1,2*j+1);//同上 //addedge(2*j+1,2*i+1); } }else{ if(c){ addedge(2*i,2*j+1); addedge(2*i+1,2*j); addedge(2*j,2*i+1); addedge(2*j+1,2*i); }else{ //addedge(2*i,2*j); //addedge(2*j,2*i); //addedge(2*i+1,2*j+1); //addedge(2*j+1,2*i+1); } } } for(i=0;i<2*n;i++) if(!dfn[i]) Tarjan(i); int flag=1; for(i=0;i<n;i++) if(belong[2*i]==belong[2*i+1]){ flag=0; break; } if(flag) puts("YES"); else puts("NO"); } return 0; }