Posts Tagged ‘2-SAT’

POJ 2723 Get Luffy Out

Posted in PKU OJ on 五月 17th, 2010 by 纳米 – Be the first to comment

2010-04-16，阅读、分析题目，Code
2010-04-17，WA（把 n = key_n << 2 写成了 n = door_n << 1），AC

题目大意：
有n对钥匙（2n条），每对钥匙仅可以使用其中一条。有m道门，每道门上有2把锁，分别对应一条钥匙，门要按照输入顺序依次打开。问最多能打开多少道门。

解题报告：
我们可以通过二分、构图，把这道题转化成为一道2-SAT判定问题。可以知道，答案具有单调性（就是如果p道门能打开，那么p-1道门必然能打开）。然后把问题转化为前p道门能否打开的问题。
如何构图呢？具体还是要看看Google上搜索到的那个ppt和pdf，把2-SAT问题如何构图搞明白，要不然我说再多也是白搭。大概文字叙述如下：
0. 对于每一条钥匙，拆分为2个点，分别代表取或不取；
1. 对于每一对钥匙，是互斥关系，就是只能取一条（取了某条必定不能取另外一条）；
2. 对于每一道门，必须打开其中一把锁（不取某条必定需要取另外一条）。其中，如果两把锁对应的钥匙相同，则该钥匙必须要取。
构图完毕后，求强连通分量，染色，判断即可解决。

代码中很多拿来检查正确性和调试的，懒得删了，都做注释了。

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
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

#include <stdio.h>
#include <string.h>
 
const int maxn = 4097, maxm = 6145;
int key_n, door_n, key[maxn][2], door[maxn][2];
int n, earr0[maxm], earr1[maxm], *e0[maxn], es0[maxn], *e1[maxn], es1[maxn];
int color[maxn], colorp, vl[maxn], vp;
 
bool input() {
	scanf("%d%d", &key_n, &door_n);
	if (!key_n && !door_n)
		return false;
	for (int i = 1; i <= key_n; ++i)
		scanf("%d%d", &key[i][0], &key[i][1]);
	for (int i = 1; i <= door_n; ++i)
		scanf("%d%d", &door[i][0], &door[i][1]);
	return true;
}
 
inline int getnum(int v, int t) {
	return (v << 1) + t;
}
 
void build_graph(int p) {
	n = key_n << 2;
	memset(es0, 0, sizeof(es0));
	memset(es1, 0, sizeof(es1));
	for (int i = 1; i <= key_n; ++i) {
		// add edge key[0].A -> key[1].B, key[1].A -> key[0].B
		++es0[getnum(key[i][0], 1)], ++es0[getnum(key[i][1], 1)];
		++es1[getnum(key[i][1], 2)], ++es1[getnum(key[i][0], 2)];
	}
	for (int i = 1; i <= p; ++i)
		if (door[i][0] != door[i][1]){
			// add edge door[0].B -> door[1].A, door[1].B -> door[0].A
			++es0[getnum(door[i][0], 2)], ++es0[getnum(door[i][1], 2)];
			++es1[getnum(door[i][1], 1)], ++es1[getnum(door[i][0], 1)];
		} else {
			// add edge door[0].B -> door[0].A
			++es0[getnum(door[i][0], 2)];
			++es1[getnum(door[i][1], 1)];
		}
	e0[0] = earr0;
	e1[0] = earr1;
	for (int i = 1; i <= n; ++i) {
		e0[i] = &e0[i-1][es0[i-1]];
		e1[i] = &e1[i-1][es1[i-1]];
	}
	memset(es0, 0, sizeof(es0));
	memset(es1, 0, sizeof(es1));
	for (int i = 1; i <= key_n; ++i) {
		// add edge key[0].A -> key[1].B, key[1].A -> key[0].B
		int u0 = getnum(key[i][0], 1), u1 = getnum(key[i][0], 2);
		int v0 = getnum(key[i][1], 1), v1 = getnum(key[i][1], 2);
		e0[u0][es0[u0]++] = v1, e0[v0][es0[v0]++] = u1;
		e1[v1][es1[v1]++] = u0, e1[u1][es1[u1]++] = v0;
//		printf("KEY %d: (%d,%d) (%d,%d)\n", i, u0, v1, v0, u1);
	}
	for (int i = 1; i <= p; ++i) {
		int u0 = getnum(door[i][0], 1), u1 = getnum(door[i][0], 2);
		int v0 = getnum(door[i][1], 1), v1 = getnum(door[i][1], 2);
		if (door[i][0] != door[i][1]){
			// add edge door[0].B -> door[1].A, door[1].B -> door[0].A
			e0[u1][es0[u1]++] = v0, e0[v1][es0[v1]++] = u0;
			e1[v0][es1[v0]++] = u1, e1[u0][es1[u0]++] = v1;
//			printf("DOOR %d: (%d,%d) (%d,%d)\n", i, u1, v0, v1, u0);
		} else {
			// add edge door[0].B -> door[0].A
			e0[u1][es0[u1]++] = v0;
			e1[v0][es1[v0]++] = u1;
//			printf("DOOR %d: (%d,%d)\n", i, u1, v0);
		}
	}
}
 
void dfs_scc_1(int u) {
	color[u] = 1;
	for (int i = 0, v = e0[u][i]; i < es0[u]; v = e0[u][++i])
		if (!color[v])
			dfs_scc_1(v);
	vl[vp--] = u;
}
 
void dfs_scc_2(int u) {
	color[u] = colorp;
	for (int i = 0, v = e1[u][i]; i < es1[u]; v = e1[u][++i])
		if (!color[v])
			dfs_scc_2(v);
}
 
bool work_check(int p) {
	build_graph(p);
	memset(color, 0, sizeof(color));
	vp = n;
	for (int v = 1; v <= n; ++v)
		if (!color[v])
			dfs_scc_1(v);
	memset(color, 0, sizeof(color));
	colorp = vp = 0;
	for (int i = 1, v = vl[1]; i <= n; v = vl[++i])
		if (!color[v]) {
			++colorp;
			dfs_scc_2(v);
		}
/*	for (int i = 1; i <= n; ++i)
		printf("color %d: %d\n", i, color[i]);*/
	for (int i = 1; i < n; i += 2)
		if (color[i] == color[i+1])
			return false;
	return true;
}
 
int work() {
	int left = 1, right = door_n, res;
	while (left <= right) {
		int mid = (left + right) >> 1;
		if (work_check(mid)) {
			res = mid;
			left = mid + 1;
		} else {
			right = mid - 1;
		}
	}
	return res;
 
/*	for (int i = 1; i <= door_n; ++i)
		printf("%d %d\n", i, work_check(i));*/
 
/*	for (int u = 1; u <= n; ++u) {
		printf("%d:", u);
		for (int i = 0, v = e0[u][i]; i < es0[u]; v = e0[u][++i])
			printf(" %d", v);
		printf("\n");
	}
	printf("\n");
	for (int u = 1; u <= n; ++u) {
		printf("%d:", u);
		for (int i = 0, v = e1[u][i]; i < es1[u]; v = e1[u][++i])
			printf(" %d", v);
		printf("\n");
	}*/
}
 
int main() {
	while (input())
		printf("%d\n", work());
	return 0;
}