UVa 12544 - Beehives

contents

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

Problem

Bees are one of the most industrious insects. Since they collect nectarand pollen from owers, they have to rely on the trees in the forest. For simplicity they numbered the n trees from 0 to n - 1. Instead of roaming around all over the forest, they use a particular list of paths. A path is based on two trees, and they can move either way i.e. from one tree to another in straight line. They don’t use paths thatare not in their list.

As technology has been improved a lot, they also changed their working strategy. Instead of hovering over all the trees in the forest, they are targeting particular trees, mainly trees with lots of owers. So, they planned that they will build some new hives in some targeted trees. After that they will only collect their foods from these trees. They will also remove some paths from their list so that they don’t have to go to a tree with no hive in it.

Now, they want to build the hives such that if one of the paths in their new list go down (some
birds or animals disturbs them in that path) it’s still possible to go from any hive to another using the existing paths.

They don’t want to choose less than two trees and as hive-building requires a lot of work, they need to keep the number of hives as low as possible. Now you are given the trees with the paths they use, your task is to propose a new bee hive colony for them.

Input

Input starts with an integer T( T < 50), denoting the number of test cases.

Each case starts with a blank line. Next line contains two integers n (2 <= n <= 500) and m (0 < m< 20000), where n denotes the number of trees and m denotes the number of paths. Each of the next m lines contains two integers uv (0 < u , v < n), u = v) meaning that there is a path between tree u and v. Assume that there can be at most one path between tree u to v, and needless to say that a path will not be given more than once in the input.

Output

For each case, print the case number and the number of beehives in the proposed colony or impossible if its impossible to find such a colony.
NOTE:
Dataset is huge. Use faster I/O methods.

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
3
3 3
0 1
1 2
2 0
2 1
0 1
5 6
0 1
1 2
1 3
2 3
0 4
3 4

Sample Output

1
2
3
Case 1: 3
Case 2: impossible
Case 3: 3

Solution

題目描述:

在一個無向圖中,找到一個成本最小環。

題目解法:

Floyd 解法:
先來附一個錯誤版本,可以在 O(n^3) 解決,核心思路在於討論路徑上經過編號小於等於 k 時,同時探討最小環上經過編號 k 個所有環。但由於 n = 500 在此題中效率不好,但也不知道為什麼拿了 Runtime Error

TLE version
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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
int g[512][512], w[512][512];
int main() {
int testcase, cases = 0;
int n, m, x, y;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
g[i][j] = w[i][j] = 0xf3f3f3f;
while(m--) {
scanf("%d %d", &x, &y);
w[x][y] = w[y][x] = g[x][y] = g[y][x] = 1;
}
int ret = 0xf3f3f3f;
for(int k = 0; k < n; k++) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(i != j)
ret = min(ret, w[k][i] + g[i][j] + w[j][k]);
}
}
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
printf("Case %d: ", ++cases);
if(ret == 0xf3f3f3f)
puts("impossible");
else
printf("%d\n", ret);
}
return 0;
}

BFS 作法:
Floyd 用在成本不同的路徑上是有效的,但是在成本都是 1 的時候就有點太過了,使用 BFS 對於每一個點進行最短路徑,查看路徑樹上是否有 back edge。整體可以在 O(n^2) 完成,這個 back edge 可能會造成有重複走過點的環,但是不影響我們去找到最小成本。

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
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
vector<int> g[512];
int dist[512], parent[512];
int bfs(int st, int &ret) {
memset(dist, 0, sizeof(dist));
dist[st] = 1, parent[st] = -1;
queue<int> Q;
Q.push(st);
while(!Q.empty()) {
int u = Q.front();
Q.pop();
for(int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if(v == parent[u]) continue;
if(dist[v] == 0) {
dist[v] = dist[u] + 1;
parent[v] = u;
Q.push(v);
} else {
ret = min(ret, dist[u] + dist[v] - 1);
}
}
}
}
int main() {
int testcase, cases = 0;
int n, m, x, y;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d %d", &n, &m);
for(int i = 0; i < n; i++)
g[i].clear();
while(m--) {
scanf("%d %d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}
int ret = n + 1;
for(int i = 0; i < n; i++)
bfs(i, ret);
printf("Case %d: ", ++cases);
if(ret == n + 1)
puts("impossible");
else
printf("%d\n", ret);
}
return 0;
}