Posts Tagged ‘二分图’

POJ 2942 Knights of the Round Table

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

2010-04-15，阅读、分析题目，学习算法，编码实现
2010-04-16，改写部分，调试，AC

好了，如果没有看了下题解，这题我是没啥思路的。

因为之前做了POJ 3177那题，然后也知道这题是双连通分量的，就直接往边双连通分量的方向想。想了半天随手画了个图出来才发现是错的，不是边双连通分量，而是点双连通分量。详细如下：

1. 构造数据给定图的补图，这才是我们所需要的，点代表骑士，边代表两个骑士愿意坐在一起。下面所有的算法都基于此图。

2. 求出图中所有的点双连通分量。对于求图中的双连通分量，还是参考byvoid牛的：图的割点、桥与双连通分支。其中，byvoid牛写到“每找到一条树枝边或后向边(非横叉边)，就把这条边加入栈中”。在我的实现中，由于只需要知道每个双连通分量的点集，所以只记录了树枝边。

还有，请无视黑书（《算法艺术与信息学竞赛》）P287上的解释，私以为那段纯属乱来。那里完全没有分开点双连通和边双连通来讨论，定义是“没有割顶的无向图又称作2-双连通分支，亦称作块”，好了，这里勉强还没有问题。后面又写：“把每个块收缩成一个点”，经过我若干时间的思考，发现边双连通分量是可以收缩的，但是点双连通分量是不可随便收缩的，因为，一个点可以同时属于两个块（点双连通分量），那么，这个点应该收缩到哪里呢？下面那句“它的边就是桥”也是有问题的，理由同上（亏他还加着重号）。这段话如果要重写，我也不知道该怎么写了，因为要多写出很多东西来，大概这样吧：：“无向图的子图中：没有割顶的子图称作点双连通分量，亦称作块。没有桥的子图称作边双连通分量，把每个边双连通分量收缩成一个点，就得到一棵树，它的边就是桥。”这样就没什么问题了。

3. 对每个双连通分量，判断是否存在奇圈（即圈上的点数为奇数）。首先给出两个定理：(1) 若某块存在奇圈，那么该块中的所有点都处于奇圈中；(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

#include <stdio.h>
#include <string.h>
 
const int maxn = 1005;
int n, m, edge[maxn][maxn], et[maxn], deep[maxn], low[maxn];
int stack[maxn][2], stack_last, bcc[maxn], bcc_n, color[maxn], color_n, answer;
bool ee[maxn][maxn], vis[maxn], point[maxn];
 
bool input() {
	scanf("%d%d", &n, &m);
	memset(et, 0, sizeof(et));
	memset(ee, 0, sizeof(ee));
	for (int i = 1, u, v; i <= m; ++i) {
		scanf("%d%d", &u, &v);
		ee[u][v] = ee[v][u] = 1;
	}
	for (int u = 1; u <= n; ++u)
		for (int v = 1; v <= n; ++v)
			if (u != v && !ee[u][v])
				edge[u][et[u]++] = v;
	return n || m;
}
 
bool fill_color(int u) {
	int new_color = (color_n << 1) + 1 - color[u];
	for (int i = 0, v = edge[u][0]; i < et[u]; v = edge[u][++i])
		if (bcc[v] == bcc_n) {
			if (color[v] < color_n) {
				color[v] = new_color;
				if (fill_color(v))
					return true;
			} else if (color[v] != new_color) {
				return true;
			}
		}
	return false;
}
 
int calc_bcc(int s, int t) {
	int last0 = stack_last++;
	++bcc_n;
	do {
		--stack_last;
		bcc[stack[stack_last][0]] = bcc[stack[stack_last][1]] = bcc_n;
	} while (stack_last > 1 && (stack[stack_last][0] != s || stack[stack_last][1] != t));
	color[s] = (color_n += 2);
	if (fill_color(s)) {
		for (int i = stack_last; i <= last0; ++i)
			point[stack[i][0]] = point[stack[i][1]] = 1;
	}
	--stack_last;
	return 0;
}
 
int dfs(int u, int father, int d) {
	int tot = 0;
	vis[u] = 1;
	deep[u] = low[u] = d;
	for (int i = 0, v = edge[u][0]; i < et[u]; v = edge[u][++i]) {
		if (!vis[v]) {
			stack[++stack_last][0] = u;
			stack[stack_last][1] = v;
			dfs(v, u, d + 1);
			++tot;
			low[u] = low[u] < low[v] ? low[u] : low[v];
			if (u == 1 || deep[u] <= low[v])
				calc_bcc(u, v);
		} else if (v != father) {
			low[u] = low[u] < deep[v] ? low[u] : deep[v];
		}
	}
	return 0;
}
 
int work() {
	memset(vis, 0, sizeof(vis));
	memset(bcc, 0, sizeof(bcc));
	memset(color, 0, sizeof(color));
	memset(point, 0, sizeof(point));
	bcc_n = color_n = stack_last = 0;
	for (int v = 1; v <= n; ++v)
		if (!vis[v])
			dfs(v, 0, 1);
	int res = 0;
	for (int v = 1; v <= n; ++v)
		res += !point[v] ? 1 : 0;
	return res;
}
 
int main() {
	while (input())
		 printf("%d\n", work());
	return 0;
}

POJ 1112 Team Them Up!

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

2009-12-03，AC

解题报告：
这题是当时体育课的时候走来走去想到的，发现真神奇我居然能想到这么神奇的东西。
进行简单的考虑，假设有A、B、C三人，A不认识B，B不认识C，那么A必然需要认识C，否则就需要3个小组了，但是题中只有2个小组。然后，可以知道，A和C一定要在同一个分组，AC和B一定不能在同一个分组。
所以，我们把所有的人按照不认识的关系构图，进行染色，判断每一个连通块能否形成二分图。不能形成二分图的，直接判无解。可以形成二分图的，由于A类结点和B类结点必须在不同的分组，所以可以简化处理：对于第i个连通块，统计A类结点的个数Ai和B类结点的个数Bi。然后进行动态规划，直接根据Ai和Bi进行计算即可。
设状态f(i, x, y)，表示在前i个连通块中，可以组成一个小组x人、另一个小组y人。有方程：f(i, x, y) = f(i-1, x-Ai, y-Bi) or f(i-1, x-Bi, y-Ai)。由于对称性，以及y可以根据i, y计算得出，可以简化为f(i, x) = f(i-1, x-Ai) or f(i-1, x-Bi)。
最后根据染色关系等等进行统计，即可得出答案。
顺便，利用位运算进行了一点小小的优化。

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

#include <stdio.h>
#include <string.h>
 
const int pow[] = {0,
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,
1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912
};
const int powW[] = {0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,
4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,
5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,
6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6
};
 
const int maxn = 103;
int n, color[maxn] = {0}, color_n, color_x, size[maxn << 1] = {0}, dpways[maxn][7] = {0}, answer_c;
bool edge[maxn][maxn] = {0}, dp[2][maxn] = {0}, answer_ok, answer[maxn];
 
int input() {
	scanf("%d", &n);
	int v;
	for (int u = 0; u < n; ++u)
		while (1) {
			scanf("%d", &v);
			if (!v)
				break;
			edge[u][v - 1] = 1;
		}
	for (int u = 0; u < n; ++u) {
		for (int v = 0; v < u; ++v)
			edge[u][v] = edge[v][u] = edge[u][v] && edge[v][u];
		edge[u][u] = 1;
	}
	return 0;
}
 
bool dye(int u) {
	int cx = color_x - color[u];
	for (int v = 0; v < n; ++v)
		if (!edge[u][v]) {
			if (color[v] == 0) {
				color[v] = cx;
				++size[cx];
				if (!dye(v))
					return false;
			} else if (color[v] != cx)
				return false;
		}
	return true;
}
 
bool work_dye() {
	color_n = 0;
	for (int i = 0; i < n; ++i)
		if (!color[i]) {
			color[i] = ++color_n;
			size[color_n] = 1;
			color_x = color_n + color_n + 1;
			if (!dye(i))
				return false;
			++color_n;
		}
	return true;
}
 
int work() {
	if (answer_ok = work_dye()) {
		dp[0][0] = true;
		int now = 0, pre = 1;
		for (int i = 1; i <= color_n; i += 2) {
			now = 1 - now;
			pre = 1 - pre;
			memset(dp[now], 0, sizeof(dp[now]));
			for (int j = n; j >= 0; --j)
				if (j - size[i] >= 0 && dp[pre][j - size[i]]) {
					dp[now][j] = true;
					memcpy(dpways[j], dpways[j - size[i]], sizeof(dpways[j]));
					dpways[j][powW[i]] |= pow[i];
				} else if (j - size[i+1] >= 0 && dp[pre][j - size[i+1]]) {
					dp[now][j] = true;
					memcpy(dpways[j], dpways[j - size[i+1]], sizeof(dpways[j]));
					dpways[j][powW[i+1]] |= pow[i+1];
				}
		}
		int arr[7];
		for (int i = n >> 1; i <= n; ++i)
			if (dp[now][i]) {
				memcpy(arr, dpways[i], sizeof(arr));
				break;
			} else if (n-i > 0 && dp[now][n-i]) {
				memcpy(arr, dpways[n-i], sizeof(arr));
				break;
			}
		answer_c = 0;
		for (int i = 0; i < n; ++i) {
			answer[i] = arr[powW[color[i]]] & pow[color[i]];
			answer_c += answer[i] ? 1 : 0;
		}
	}
	return 0;
}
 
int output() {
	if (answer_ok) {
		printf("%d", answer_c);
		for (int i = 0; i < n; ++i)
			if (answer[i])
				printf(" %d", i + 1);
		printf("\n%d", n - answer_c);
		for (int i = 0; i < n; ++i)
			if (!answer[i])
				printf(" %d", i + 1);
		printf("\n");
	} else
		printf("No solution\n");
	return 0;
}
 
int main() {
	input();
	work();
	output();
	return 0;
}