【例3-3】医院设置

题目描述

给定 n 个结点的二叉树，结点 i 住 p_i 人，左、右孩子为 l_i、r_i（0 表示无孩子）。相邻结点距离为 1，要在某一结点建医院，使所有居民到医院的距离之和最小。输入：第一行 n；接下来 n 行每行 p_i、l_i、r_i。输出：最小距离和。n ≤ 100。样例输入：5 / 13 2 3 / 4 0 0 / 12 4 5 / 20 0 0 / 40 0 0，样例输出：81

思路

把父子链接当作无向边，Floyd 求全源最短路；枚举医院位置，按人口加权求距离和，取最小值。

参考代码

Python 版：

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
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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 05:57
# update_at: 2026-10-12 14:53

# 二叉树结点的存储 + Floyd 全源最短路：
# 一个结点的三个字段聚合成 Node 对象：人口、左链接、右链接（0 表示无链接）。
# 如何使用：
# 1. 读入第 i 行：node[i].pop / lch / rch 赋值
# 2. 把链接当无向边写进距离矩阵 d（初始自己到自己 0，其余 INF）
# 3. Floyd 求出 d[u][v] 后枚举医院位置 u，取 sum(pop[v] * d[u][v]) 的最小值

import sys

INF = 10 ** 9  # 距离上界：边权为 1，实际距离远小于它


class Node:
    """编号 u 的结点：人口 + 左右链接（0 表示无链接）。"""

    def __init__(self) -> None:
        self.pop = 0  # 居民人口数
        self.lch = 0  # 左链接指向的结点编号，0 表示无链接
        self.rch = 0  # 右链接指向的结点编号，0 表示无链接


node: list[Node] = []    # node[u]：编号 u 的结点
d: list[list[int]] = []  # d[u][v]：u 到 v 的最少边数


def init(n: int) -> None:
    """造出 0..n 共 n+1 个结点，距离矩阵先设成"自己到自己 0，其余 INF"。"""
    global node, d
    node = [Node() for _ in range(n + 1)]
    d = [[0 if u == v else INF for v in range(n + 1)] for u in range(n + 1)]


def build_edges(n: int) -> None:
    """把结点里的左右链接翻译成无向边（相邻距离 1）：链接是双向可走的。"""
    for i in range(1, n + 1):
        for child in (node[i].lch, node[i].rch):
            if child:
                d[i][child] = d[child][i] = 1


def floyd(n: int) -> None:
    """Floyd 全源最短路：d[u][v] 是 u 到 v 的最少边数。"""
    for k in range(1, n + 1):
        d_k = d[k]                       # 缓存第 k 行，省掉内层重复索引
        for d_i in d[1:]:
            d_ik = d_i[k]
            for j in range(1, n + 1):
                if d_i[j] > d_ik + d_k[j]:
                    d_i[j] = d_ik + d_k[j]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)

    init(n)
    for i in range(1, n + 1):
        node[i].pop = next(data)
        node[i].lch = next(data)
        node[i].rch = next(data)

    build_edges(n)
    floyd(n)

    # 医院可以建在任意结点上，枚举每个候选 u 求"人口 x 距离"的总和，取最小
    print(min(sum(node[v].pop * d[u][v] for v in range(1, n + 1)) for u in range(1, n + 1)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 10:38
 * update_at: 2026-10-12 14:56
 */
// main.cpp：把二叉树的父子链接当无向边，Floyd 求全源最短路，枚举医院位置取最小距离和。
//
// 结点的三个字段聚合成 struct：人口、左链接、右链接（0 表示无链接）。
// Floyd 用的距离矩阵 d[u][v] 是结点两两之间的关系，不属于某个结点的字段，
// 单独开全局二维数组，不和 Node 混在一起。

#include <iostream>

using namespace std;

typedef long long ll;

const int maxn = 105; // 题面 n <= 100，按上界开
const ll INF = 1e9;   // 距离上界：边权为 1，实际距离远小于它

struct Node {
    ll pop;  // 结点的居民人口数
    int lch; // 左链接指向的结点编号，0 表示无链接
    int rch; // 右链接指向的结点编号，0 表示无链接
};

Node node[maxn];   // node[u]：编号 u 的结点
ll d[maxn][maxn];  // d[u][v]：u 到 v 的最少边数
ll n;              // 结点数

// 读入每个结点的人口和左右链接
void read_input() {
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> node[i].pop >> node[i].lch >> node[i].rch;
    }
}

// 初始化全源距离矩阵：自己到自己为 0，其余先设成 INF 等着被边更新
void init_dist() {
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= n; j++) {
            d[i][j] = (i == j) ? 0 : INF;
        }
    }
}

// 把结点里的链接翻译成无向边（相邻距离 1）：链接是双向可走的
void build_edges() {
    for (ll i = 1; i <= n; i++) {
        if (node[i].lch != 0) {
            d[i][node[i].lch] = d[node[i].lch][i] = 1;
        }
        if (node[i].rch != 0) {
            d[i][node[i].rch] = d[node[i].rch][i] = 1;
        }
    }
}

// Floyd 全源最短路：枚举中转点 k，尝试用 i -> k -> j 缩短 i -> j
void floyd() {
    for (ll k = 1; k <= n; k++) {
        for (ll i = 1; i <= n; i++) {
            for (ll j = 1; j <= n; j++) {
                if (d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
}

// 医院可以建在任意结点：枚举每个候选 u，求"人口 x 距离"的总和，取最小
ll min_total_distance() {
    ll ans = INF * INF; // 总路程的答案上界
    for (ll u = 1; u <= n; u++) {
        ll sum = 0;
        for (ll v = 1; v <= n; v++) {
            sum += node[v].pop * d[u][v];
        }
        if (sum < ans) {
            ans = sum;
        }
    }
    return ans;
}

void solve() {
    read_input();
    init_dist();
    build_edges();
    floyd();
    cout << min_total_distance() << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();
    return 0;
}

【例3-3】医院设置

目录

题目描述

思路

参考代码