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了 借用別人的解題報(bào)告

思路：因?yàn)榻o出結(jié)點(diǎn) a ，b，值 c，還有判斷方式OP，這種一看當(dāng)然就知道是用2SAT做了。為什么說(shuō)是深刻理解2SAT呢，因?yàn)椤?SAT中說(shuō)過(guò)，只有關(guān)系確定的才能連邊，否則不能連邊；還有一個(gè)重要的是，如果某個(gè)條件必須為某個(gè)值時(shí)，自身與自身的相反條件也要連邊，具體看下面解釋：

現(xiàn)在設(shè) 2*a為1，2*a+1為0；當(dāng)然 2*b為1，2*b+1為0：

1.當(dāng)OP為’And‘時(shí)：

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

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

2.當(dāng)OP為OR時(shí)，

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

（2）當(dāng)c=0時(shí)，那么只有當(dāng)a=b=0這個(gè)關(guān)系，所以這個(gè)和上面1（1）情況就一樣了，上面是強(qiáng)制執(zhí)行a=b=1的情況，而這里因?yàn)橹挥衋=b=0的情況，所以也要強(qiáng)制執(zhí)行a=b=0,即連邊：<2*a,2*a+1>,<2*b,2*b+1>。

3.當(dāng)OP為XOR時(shí)，因?yàn)槿绻鸻=1,那么b必=0；a=0，b必=1；b=1，a必=0；b=0，a必=1。如此看，這四個(gè)關(guān)系都是確定的，所以都要連邊，但是其實(shí)我們可以不連，一條邊都不用連，因?yàn)槌鯽=1的時(shí)候一定不會(huì)再出現(xiàn)a=0了，這四條邊是不會(huì)產(chǎn)生矛盾的，所以強(qiáng)連通縮點(diǎn)后不會(huì)出現(xiàn)belong[2*a]=belong[2*a+1]的情況的，所以連了也沒(méi)用，只是多加了點(diǎn)判斷的時(shí)間罷了……這在別人的解題報(bào)告里說(shuō)的是形成了組環(huán)了，都是一個(gè)意思。比如：a=1,b=0與b=0,a=1在tarjan中會(huì)形成一個(gè)新的結(jié)點(diǎn)，也就是自環(huán)，所以……在異或這種情況中只能選擇a=0或者a=1，所以不會(huì)出現(xiàn)矛盾……故不用連邊了！

1 #pragma comment(linker, "/STACK:1024000000,1024000000") 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<cmath> 6 #include<math.h> 7 #include<algorithm> 8 #include<queue> 9 #include<set> 10 #include<bitset> 11 #include<map> 12 #include<vector> 13 #include<stdlib.h> 14 #include <stack> 15 using namespace std; 16 #define PI acos(-1.0) 17 #define max(a,b) (a) > (b) ? (a) : (b) 18 #define min(a,b) (a) < (b) ? (a) : (b) 19 #define ll long long 20 #define eps 1e-10 21 #define MOD 1000000007 22 #define N 1006 23 #define inf 1e12 24 int n,m; 25 vector<int> e[N]; 26 27 int tot; 28 int head[N]; 29 int vis[N]; 30 int tt; 31 int scc; 32 stack<int>s; 33 int dfn[N],low[N]; 34 int col[N]; 35 struct Node 36 { 37 int from; 38 int to; 39 int next; 40 }edge[N*N]; 41 void init() 42 { 43 tot=0; 44 scc=0; 45 tt=0; 46 memset(head,-1,sizeof(head)); 47 memset(dfn,-1,sizeof(dfn)); 48 memset(low,0,sizeof(low)); 49 memset(vis,0,sizeof(vis)); 50 memset(col,0,sizeof(col)); 51 } 52 void add(int s,int u)//鄰接矩陣函數(shù) 53 { 54 edge[tot].from=s; 55 edge[tot].to=u; 56 edge[tot].next=head[s]; 57 head[s]=tot++; 58 } 59 void tarjan(int u)//tarjan算法找出圖中的所有強(qiáng)連通分支 60 { 61 dfn[u] = low[u]= ++tt; 62 vis[u]=1; 63 s.push(u); 64 int cnt=0; 65 for(int i=head[u];i!=-1;i=edge[i].next) 66 { 67 int v=edge[i].to; 68 if(dfn[v]==-1) 69 { 70 // sum++; 71 tarjan(v); 72 low[u]=min(low[u],low[v]); 73 } 74 else if(vis[v]==1) 75 low[u]=min(low[u],dfn[v]); 76 } 77 if(dfn[u]==low[u]) 78 { 79 int x; 80 scc++; 81 do{ 82 x=s.top(); 83 s.pop(); 84 col[x]=scc; 85 vis[x]=0; 86 }while(x!=u); 87 } 88 } 89 bool two_sat(){ 90 91 for(int i=0;i<2*n;i++){ 92 if(dfn[i]==-1){ 93 tarjan(i); 94 } 95 } 96 for(int i=0;i<n;i++){ 97 if(col[2*i]==col[2*i+1]){ 98 return false; 99 } 100 } 101 return true; 102 } 103 int main() 104 { 105 while(scanf("%d%d",&n,&m)==2){ 106 init(); 107 for(int i=0;i<N;i++) e[i].clear(); 108 while(!s.empty()){ 109 s.pop(); 110 } 111 int a,b,c; 112 char s[6]; 113 for(int i=0;i<m;i++){ 114 scanf("%d%d%d%s",&a,&b,&c,s); 115 if(s[0]=='A'){ 116 if(c==1){ 117 //e[2*a+1].push_back(2*a); 118 //e[2*b+1].push_back(2*b); 119 add(2*a+1,2*a); 120 add(2*b+1,2*b); 121 } 122 else{ 123 //e[2*a].push_back(2*b+1); 124 //e[2*b].push_back(2*a+1); 125 add(2*a,2*b+1); 126 add(2*b,2*a+1); 127 } 128 } 129 else if(s[0]=='O'){ 130 if(c==1){ 131 //e[2*a+1].push_back(2*b); 132 //e[2*b+1].push_back(2*a); 133 add(2*a+1,2*b); 134 add(2*b+1,2*a); 135 } 136 else{ 137 //e[2*a].push_back(2*a+1); 138 //e[2*b].push_back(2*b+1); 139 add(2*a,2*a+1); 140 add(2*b,2*b+1); 141 } 142 } 143 } 144 if(two_sat()){ 145 printf("YES\n"); 146 } 147 else{ 148 printf("NO\n"); 149 } 150 } 151 return 0; 152 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/UniqueColor/p/4814122.html

總結(jié)

以上是生活随笔為你收集整理的poj 3678 Katu Puzzle(2-sat)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。