学海泛舟

poj 3678 Katu Puzzle 题解

发表于 | 分类于 |

原题

传送门

题目大意

有一张n个点，m条边的图，每条边上有一个布尔运算符（AND，OR，XOR）和一个布尔值，问是否能在点上填入合适的布尔值，使得任意一条边所连接的两个点的布尔值经过边上的运算符运算后等于边上的布尔值。

分析

将每个点拆成两个点，分别代表取0和取1.
边连接的两个点，一共只有四种状态，即（1，0），（0，1），（0，0），（1，1）。找到不符合条件的状态，就是冲突的地方。这样就回归了2-SAT的基本模型了。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<map>
#include<climits>
#include<cmath>
using namespace std;
const int maxn=5500;
struct Edge{
	int to,next;
}edge[6000005];
int head[maxn],tot;
void addedge(int u,int v){
	edge[tot].to=v;
	edge[tot].next=head[u];
	head[u]=tot++;
}
int scc,Low[maxn],DFN[maxn],Stack[maxn],top,Index,Belong[maxn];
bool Instack[maxn];
void tarjan(int u){
	int v;
	Low[u]=DFN[u]=++Index;
	Stack[top++]=u;
	Instack[u]=true;
	for(int i=head[u];~i;i=edge[i].next){
		v=edge[i].to;
		if(!DFN[v]){
			tarjan(v);
			if(Low[u]>Low[v]) Low[u]=Low[v];
		} else if(Instack[v]&&Low[u]>DFN[v])
			Low[u]=DFN[v];
	}
	if(Low[u]==DFN[u]){
		scc++;
		do{
			v=Stack[--top];
			Instack[v]=false;
			Belong[v]=scc;
		} while(v!=u);
	}
}
void solve(int N){
	memset(DFN,0,sizeof DFN);
	memset(Instack,false,sizeof Instack);
	Index=scc=top=0;
	for(int i=0;i<N;++i)
		if(!DFN[i])
			tarjan(i);
}
void init(){
	tot=0;
	memset(head,-1,sizeof head);
}
int main(){
	int N,M;
	while(scanf("%d %d",&N,&M)!=EOF){
		init();
		char s[10];
		for(int i=0;i<M;++i){
			int a,b,c;
			scanf("%d %d %d %s",&a,&b,&c,&s);
			if(c==0){
				if(s[0]=='A'){
					addedge(b<<1|1,a<<1);
					addedge(a<<1|1,b<<1);
				} else if(s[0]=='O'){
					addedge(a<<1|1,b<<1|1);
					addedge(b<<1,a<<1);
					addedge(a<<1|1,b<<1);
					addedge(b<<1|1,a<<1);
					addedge(a<<1,b<<1);
					addedge(b<<1|1,a<<1|1);
				} else if(s[0]=='X'){
					addedge(a<<1,b<<1);
					addedge(b<<1|1,a<<1|1);
					addedge(a<<1|1,b<<1|1);
					addedge(b<<1,a<<1);
				}
			} else if(c==1){
				if(s[0]=='A'){
					addedge(a<<1|1,b<<1|1);
					addedge(b<<1,a<<1);
					addedge(a<<1,b<<1);
					addedge(b<<1|1,a<<1|1);
					addedge(a<<1,b<<1|1);
					addedge(b<<1,a<<1|1);
				} else if(s[0]=='O'){
					addedge(a<<1,b<<1|1);
					addedge(b<<1,a<<1|1);
				} else if(s[0]=='X'){
					addedge(a<<1,b<<1|1);
					addedge(b<<1,a<<1|1);
					addedge(a<<1|1,b<<1);
					addedge(b<<1|1,a<<1);
				}
			}
		}
		solve(2*N);
		bool flag=true;
		for(int i=0;i<2*N;i+=2){
			if(Belong[i]==Belong[i^1]){
				flag=false;
				break;
			}
		}
		if(flag) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}