UVa 12684 - VivoParc

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

動物園的 4 種動物配置,動物都有地域性,不希望相鄰的地方會具有與自己相同的物種。

給一個 graph,最多用四個顏色著色,使得相鄰不同色,輸出任意種方案即可。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
8
1-2
3-1
4-5
4-8
1-7
1-4
7-1
2-4
1-8
6-7
2-3
1-5
1-6
7-6
7-8
2-5
7-1
3-4
5-6
7-8

Sample Output

1
2
3
4
5
6
7
8
1 4
2 2
3 1
4 3
5 1
6 2
7 1
8 2

Solution

看起來 N 還算大,窮舉順序會稍微影響速度,依序窮舉節點,檢查是否存在相鄰同色。由於不曉得是不是只有一個連通元件,連通元件分開找解,防止浪費時間的搜索。

接著根據 bfs 順序進行窮舉,來加快退回的速度。事實上也發現到四色問題如果保證有解,事實上應該很容易找到其中一組解。

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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<int> g[128];
int visited[128];
int A[128], An, color[128];
int used[128];
int dfs(int idx) {
if (idx == An)
return 1;
for (int c = (idx == 0 ? 4 : 1); c <= 4; c++) {
int u = A[idx], v, ok = 1;
for (int i = 0; i < g[u].size() && ok; i++) {
v = g[u][i];
if (used[v] && color[v] == c)
ok = 0;
}
if (ok) {
used[u] = 1;
color[u] = c;
if (dfs(idx+1))
return 1;
used[u] = 0;
}
}
return 0;
}
void bfs(int st) {
queue<int> Q;
int u;
An = 0;
Q.push(st), visited[st] = 1;
while (!Q.empty()) {
u = Q.front(), Q.pop();
A[An++] = u;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (visited[v] == 0) {
visited[v] = 1;
Q.push(v);
}
}
}
memset(used, 0, sizeof(used));
dfs(0);
}
int main() {
char line[128];
int x, y, n, cases = 0;
while (scanf("%d", &n) == 1) {
while (getchar() != '\n');
for (int i = 0; i <= n; i++)
g[i].clear();
while (gets(line)) {
if (line[0] == '\0')
break;
sscanf(line, "%d-%d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
sort(g[i].begin(), g[i].end());
g[i].resize(distance(g[i].begin(), unique(g[i].begin(), g[i].end())));
}
memset(visited, 0, sizeof(visited));
for (int i = 1; i <= n; i++) {
if (visited[i] == 0) {
bfs(i);
}
}
if (cases++) puts("");
for (int i = 1; i <= n; i++)
printf("%d %d\n", i, color[i]);
}
return 0;
}
/*
8
1-2
3-1
4-5
4-8
1-7
1-4
7-1
2-4
1-8
6-7
2-3
1-5
1-6
7-6
7-8
2-5
7-1
3-4
5-6
7-8
*/