UVa 1267 - Network

contents

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

Problem

有一個 N 節點的樹,要架設服務的 server,必須滿足所有葉節點到最近的 server 距離小於等於 M。一開始會給定一個架好的 server。

求最少的放置個數。

Sample Input

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
2 14 
12 2
1 2
2 3
3 4
4 5
5 6
7 5
8 5
4 9
10 3
2 12
12 14
13 14
14 11
14
3 4
1 2
2 3
3 4
4 5
5 6
7 5
8 5
4 9
10 3
2 12
12 14
13 14
14 11

Sample Output

1
2
1 
0

Solution

針對加好的 server,將這個 server 當作 root,將 tree 轉換成 rooted tree,接著使用貪心。

盡可能放置越遠越好,根據 dfs 搜索的順序,查看內部節點 u,其子樹最遠的葉節點深度為何,以及子樹內部距離最近的 server 所在。

共計三種可能

  • 節點 u 逼不得已情況下放置 server
  • 節點 u 無須 server,其子樹的葉節點都已經符合標準
  • 節點 u 無須 server,其子樹的葉節點必須靠另外一個子樹的最近 server 服務。
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
#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;

vector<int> g[1024];
int n, m, s, x, y;
int ret = 0;
int dfs(int u, int p, int dep, int &place) {
int leaf = 0, pp = 0x3f3f3f3f;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (v == p)
continue;
int p;
int tmp = dfs(v, u, dep + 1, p);
pp = min(p, pp);
leaf = max(leaf, tmp);
}
place = pp;
if (leaf - dep + pp - dep <= m)
leaf = 0;
if (leaf == dep + m) {
place = dep;
ret += (u != s), leaf = 0/*, printf("place %d, %d\n", u, place)*/;
}
if (g[u].size() == 1)
return dep;
else
return leaf;
}
int main() {
int testcase;
scanf("%d", &testcase);
while (testcase--) {
scanf("%d %d %d", &n, &s, &m);
for (int i = 0; i <= n; i++)
g[i].clear();
for (int i = 1; i < n; i++) {
scanf("%d %d", &x, &y);
g[x].push_back(y);
g[y].push_back(x);
}

ret = 0;
int foo;
dfs(s, -1, 0, foo);
printf("%d\n", ret);
}
return 0;
}
/*
2
14 12 2
1 2
2 3
3 4
4 5
5 6
7 5
8 5
4 9
10 3
2 12
12 14
13 14
14 11

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