解題區/解題區 - UVa

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
*/