解題區/解題區 - UVa

UVa 12862 - Intrepid climber

contents

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

Problem

從山頂往下爬不需要花費，往上爬則要根據給定的邊上的花費計算。現在有朋友在特定的點上，找到一條花費最少的路徑。(花費計算到抵達最後一個朋友的所在地，不用特地返回山頂。)

給定的圖為一棵樹。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
6 2
1 2 2
2 4 2
1 3 3
3 6 3
3 5 1
5 2
4 2
1 2 2
1 3 1
3 4 2
2 4
4 2
1 4 1
1 3 1
4 2 2
2 4

Sample Output

1
2
3
2
2
0

Solution

如果把最後停留的點再走回去山頂，則會構成一個尤拉環道，而在這一題可以觀察出這個尤拉環道的花費是固定的。

那麼要找停留的地方，必然是扣除返回山頂的最大花費，這樣就能找到拜訪所有朋友的最小花費。對於某些朋友可能不是在葉節點，如果其子樹內沒有朋友，就可以不用走訪。概念上，需要將這個樹稍微壓縮一下。

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
#include <stdio.h> 
#include <vector>
#include <algorithm>
using namespace std;
vector< pair<int, int> > g[131072];
int f[131072], w = 0, ret = 0;
void dfs(int u, int &friends, int dep) {
    int v, ff = 0, cost;
    friends = f[u];
    if (f[u])	ret = max(ret, dep);
    for (int i = 0; i < g[u].size(); i++) {
        v = g[u][i].first;
        dfs(v, ff, dep + g[u][i].second);
        if (ff > 0) {
            w += g[u][i].second;
            friends += ff;
        }
    }
}
int main() {
    int n, m, x, y, v;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 1; i <= n; i++)
            g[i].clear(), f[i] = 0;
        for (int i = 1; i < n; i++) {
            scanf("%d %d %d", &x, &y, &v);
            g[x].push_back(make_pair(y, v));
        }
        for (int i = 0; i < m; i++) {
            scanf("%d", &x);
            f[x] = 1;
        }
        w = 0, ret = 0;
        dfs(1, x, 0);
        printf("%d\n", w - ret);
    }
    return 0;
}
/*
6 2
1 2 2
2 4 2
1 3 3
3 6 3
3 5 1
5 2
4 2
1 2 2
1 3 1
3 4 2
2 4
4 2
1 4 1
1 3 1
4 2 2
2 4
*/