学海泛舟

hihoCoder 1467 2-SAT·hihoCoder音乐节 题解

发表于 | 分类于 |

原题

传送门

题目大意

有n首歌可以在上午放或下午放，但只能放一次，每个评委有两个要求，满足其中任意一个，评委就会满意，问能否使所有评委都满意。

分析

因为只要满足任意一个要求，就能满足，所以这两个要求之间的关系为OR。又因为每个评委都要满意，所以评委之间的关系为AND，问题就转为是否能让表达式为真。不妨将歌在上午放记为x，将歌在下午放记为~x，这样表达式就能写出了。接下考虑如何寻找表达式的解。
可以将这个问题转化为一个图论的问题。a OR b可以转变为~a->b AND ~b->a，将每首歌拆成两个点，一个代表a，另一个代表~a，根据关系连有向边。例如上面的例子，应该从~a连向b，和从~b连向a，这样就构成了一张有向图。只要任意一个点拆出的两个点都不在同一个联通块中，就代表能使所有评委满意。

参考代码

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
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<map>
#include<climits>
using namespace std;
struct Edge{
	int to,next;
}edge[5000];
int head[500];
int tot;
void addedge(int u,int v){
	edge[tot].to=v;
	edge[tot].next=head[u];
	head[u]=tot++;
}
void init(){
	tot=0;
	memset(head,0xff,sizeof head);
}
int Low[500],DFN[500],Stack[500],Belong[500];
int Index,top;
int scc;
bool Instack[500];
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);
	}
}
int main(){
	int k;
	scanf("%d",&k);
	while(k--){
		int n,m;
		scanf("%d %d",&n,&m);
		char a[10],b[10];
		init();
		for(int j=1;j<=m;++j){
			scanf("%s %s",a,b);
			int u=0,v=0;
			for(int i=1;i<strlen(a);++i){
				u=u*10+a[i]-'0';
			}
			if(a[0]=='m'){
				u=2*(u-1);
			} else {
				u=2*(u-1)+1;
			}
			for(int i=1;i<strlen(b);++i){
				v=v*10+b[i]-'0';
			}
			if(b[0]=='m'){
				v=2*(v-1);
			} else {
				v=2*(v-1)+1;
			}
			addedge((u^1),v);
			addedge((v^1),u);
		}
		solve(2*n);
		bool flag=1;
		for(int i=0;i<n;++i){
			if(Belong[2*i]==Belong[2*i+1]){
				flag=0;
				break;
			}
		}
		if(flag){
			printf("GOOD\n");
		} else {
			printf("BAD\n");
		}
	}
	return 0;
}