医院设置

题意

树上每个节点有居民数。选择一个节点建医院，代价是所有节点人口乘到医院距离之和，求最小代价。

思路

n<=100，直接枚举医院位置。对每个候选点 BFS 求到全树距离，再计算：

\sum population_i\times distance_i

树中两点路径唯一，BFS 第一次到达的层数就是边数距离。取所有候选代价的最小值即可。

Python 知识

邻接表用列表推导式创建，每条父子边双向加入。
map(total_distance,range(1,n+1)) 产生每个候选医院的代价，min 直接聚合。
deque 与距离列表完成单源 BFS。
/home/rainboy/mycode/hugo-blog/content/program_language/python/bfs_shortest.md：树也可视为无权图进行 BFS。
/home/rainboy/mycode/hugo-blog/content/program_language/python/map_reduce_filter.md：命名函数与 map/min 组合。

代码

python

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
34import sys
from collections import deque


input = sys.stdin.buffer.readline
n = int(input())
population = [0] * (n + 1)
tree = [[] for _ in range(n + 1)]

for node in range(1, n + 1):
    weight, left, right = map(int, input().split())
    population[node] = weight
    for child in (left, right):
        if child:
            tree[node].append(child)
            tree[child].append(node)


def total_distance(start):
    distance = [-1] * (n + 1)
    distance[start] = 0
    queue = deque([start])
    total = 0
    while queue:
        node = queue.popleft()
        total += population[node] * distance[node]
        for neighbor in tree[node]:
            if distance[neighbor] == -1:
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)
    return total


print(min(map(total_distance, range(1, n + 1))))

cpp

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/**
 * P1364 医院设置
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;
const int INF = 0x3f3f3f3f;

// 邻接表建无向树
int head[MAXN], to[MAXN * 2], nxt[MAXN * 2], edge_cnt;
int w[MAXN]; // 各结点人口数
int n;

void add_edge(int u, int v) {
    ++edge_cnt;
    to[edge_cnt] = v;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}

// BFS 求从 start 出发到所有点的距离总和
int bfs(int start) {
    int dist[MAXN];
    memset(dist, -1, sizeof(dist));
    dist[start] = 0;
    queue<int> q;
    q.push(start);
    int sum = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        sum += w[u] * dist[u]; // 人口 × 距离
        for (int i = head[u]; i; i = nxt[i]) {
            int v = to[i];
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return sum;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int l, r;
        scanf("%d%d%d", &w[i], &l, &r);
        if (l) { add_edge(i, l); add_edge(l, i); }
        if (r) { add_edge(i, r); add_edge(r, i); }
    }
    int ans = INF;
    for (int i = 1; i <= n; ++i) ans = min(ans, bfs(i));
    printf("%d\n", ans);
    return 0;
}

复杂度

每个候选 BFS 为 $O(n)$ ，共 n 个候选，总时间 $O(n^2)$ ，空间 $O(n)$ 。

总结

小规模优化题先考虑直接枚举候选并准确计算代价；树的唯一路径让每次 BFS 很简单。

目录

题意

思路

Python 知识

代码

复杂度

总结