AcWing 1255. 医院设置
宋标 Lv5
  2022-08-18 02:30:49 2022-08-18 02:30    

题目

设有一棵二叉树（如下图），其中圈中的数字表示结点中居民的人口，圈边上数字表示结点编号。

现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻结点之间的距离为 。

就本图而言，若医院建在 处，则距离和为 ；若医院建在 处，则距离和为 。

11.png

输入格式

第一行一个整数 ，表示树的结点数。

接下来的 行每行描述了一个结点的状况，其中第 行，描述结点 的具体状况，包含三个整数，整数之间用空格（一个或多个）分隔，其中：第一个数为居民人口数；第二个数为左链接结点编号，为 表示无链接；第三个数为右链接结点编号，为 表示无链接。

树的结点编号从 到 。

输出格式

一个整数，表示最小距离和。

数据范围

，
每个地点的居民人口数均不超过100。

输入样例：

5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0

输出样例：

81

题解

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
#include <iostream>
#include <cstring>
#define N 110

using namespace std;

int cnt[N];
int h[N], e[N * 2], ne[N * 2], idx;
int n;

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

int dfs(int u, int f, int d)
{
    int sum = cnt[u] * d;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == f) continue;
        sum += dfs(j, u, d + 1);
    }

    return sum;
}

int main()
{
    memset(h, -1, sizeof h);

    cin >> n;
    for (int i = 1; i <= n; ++ i)
    {
        int l, r;
        cin >> cnt[i] >> l >> r;
        if (l) add(i, l), add(l, i);
        if (r) add(i, r), add(r, i);
    }

    int res = 1e9;

    for (int i = 1; i <= n; ++ i) res = min(res, dfs(i, -1, 0));

    cout << res << endl;

    return 0;
}
 评论