解題區/解題區 - UVa

UVa 12379 - Central Post Office

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
2
2
1 2
1 1
5
3 2 3 4
1 1
2 1 5
1 1
1 3

Sample Output

1
2
1
5

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
#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
// euler path
#define MAXN 10005
int dist[MAXN], visited[MAXN];
vector<int> g[MAXN];
void dfs(int u) {
    visited[u] = 1;
    for(int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (visited[v]) continue;
        dist[v] = dist[u]+1;
        dfs(v);
    }
}
int tree_diameter(int n) {
    memset(visited, 0, sizeof(visited));
    dist[1] = 0, dfs(1);
    
    int p = (int)(max_element(dist + 1, dist + n + 1) - dist);
    memset(visited, 0, sizeof(visited));
    dist[p] = 0, dfs(p);
    return *(max_element(dist + 1, dist + n + 1));
}
int main() {
    int testcase, n, m, x;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &m);
            g[i].clear();
            for (int j = 0; j < m; j++) {
                scanf("%d", &x);
                g[i].push_back(x);
            }
        }
        printf("%d\n", (2 * n - 2) - tree_diameter(n));
    }
    return 0;
}