【题目来源】
洛谷：P1364 医院设置 - 洛谷
【题目描述】
设有一棵二叉树，如图：
其中，圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为 \(1\)。如上图中，若医院建在 \(1\) 处，则距离和 \(=4+12+2\times20+2\times40=136\)；若医院建在 \(3\) 处，则距离和 \(=4\times2+13+20+40=81\)。
【输入】
第一行一个整数 \(n\)，表示树的结点数。
接下来的 \(n\) 行每行描述了一个结点的状况，包含三个整数 \(w, u, v\)，其中 \(w\) 为居民人口数，\(u\) 为左链接（为 \(0\) 表示无链接），\(v\) 为右链接（为 \(0\) 表示无链接）。
【输出】
一个整数，表示最小距离和。
【输入样例】
5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0
【输出样例】
81
【算法标签】
《洛谷 P1364 医院设置》 #动态规划DP# #树形数据结构# #广度优先搜索BFS# #最短路# #树的重心#
【代码详解】
#include <bits/stdc++.h>
using namespace std;
const int N = 105, M = N * 2; // 定义常量，N: 最大节点数，M: 最大边数
int n, w[N], u, v, ans = 1e9, sum, dep[N]; // n: 节点数, w: 节点权重, ans: 最小总代价
int h[N], e[M], ne[M], idx; // 邻接表存储树
void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx++; // 添加无向边
}
// DFS计算深度
void dfs(int u, int fa) // u: 当前节点, fa: 父节点
{if (fa) // 如果有父节点dep[u] = dep[fa] + 1; // 当前节点深度 = 父节点深度 + 1for (int i = h[u]; i != -1; i = ne[i]) // 遍历当前节点的所有邻接点{int j = e[i]; // 邻接节点jif (j == fa) continue; // 如果是父节点，跳过dfs(j, u); // 递归遍历子节点}
}
int main()
{memset(h, -1, sizeof(h)); // 初始化邻接表cin >> n; // 输入节点数// 输入每个节点的权重和子节点for (int i = 1; i <= n; i++){cin >> w[i] >> u >> v; // 权重, 左子节点, 右子节点if (u) // 如果有左子节点add(i, u), add(u, i); // 添加双向边if (v) // 如果有右子节点add(i, v), add(v, i); // 添加双向边}// 尝试每个节点作为根for (int i = 1; i <= n; i++){sum = 0; // 重置总代价memset(dep, 0, sizeof(dep)); // 重置深度数组dfs(i, 0); // 以i为根进行DFS，计算各节点深度// 计算以i为根的总代价for (int j = 1; j <= n; j++)sum += w[j] * dep[j]; // 代价 = 权重 × 深度ans = min(ans, sum); // 更新最小代价}cout << ans << endl; // 输出结果return 0;
}
【运行结果】
5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0
81