算法竞赛备考冲刺必刷题（C++） | 洛谷 P1364 医院设置

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：P1364 医院设置 - 洛谷

【题目描述】

设有一棵二叉树，如图：

其中，圈中的数字表示结点中居民的人口。圈边上数字表示结点编号，现在要求在某个结点上建立一个医院，使所有居民所走的路程之和为最小，同时约定，相邻接点之间的距离为1 11。如上图中，若医院建在1 11处，则距离和= 4 + 12 + 2 × 20 + 2 × 40 = 136 =4+12+2\times20+2\times40=136=4+12+2×20+2×40=136；若医院建在3 33处，则距离和= 4 × 2 + 13 + 20 + 40 = 81 =4\times2+13+20+40=81=4×2+13+20+40=81。

【输入】

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

接下来的n nn行每行描述了一个结点的状况，包含三个整数w , u , v w, u, vw,u,v，其中w ww为居民人口数，u uu为左链接（为0 00表示无链接），v vv为右链接（为0 00表示无链接）。

【输出】

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

【输入样例】

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

【输出样例】

81

【算法标签】

《洛谷 P1364 医院设置》 #动态规划DP# #树形数据结构# #广度优先搜索BFS# #最短路# #树的重心#

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=105,M=N*2;// 定义常量，N: 最大节点数，M: 最大边数intn,w[N],u,v,ans=1e9,sum,dep[N];// n: 节点数, w: 节点权重, ans: 最小总代价inth[N],e[M],ne[M],idx;// 邻接表存储树voidadd(inta,intb){e[idx]=b,ne[idx]=h[a],h[a]=idx++;// 添加无向边}// DFS计算深度voiddfs(intu,intfa)// u: 当前节点, fa: 父节点{if(fa)// 如果有父节点dep[u]=dep[fa]+1;// 当前节点深度 = 父节点深度 + 1for(inti=h[u];i!=-1;i=ne[i])// 遍历当前节点的所有邻接点{intj=e[i];// 邻接节点jif(j==fa)continue;// 如果是父节点，跳过dfs(j,u);// 递归遍历子节点}}intmain(){memset(h,-1,sizeof(h));// 初始化邻接表cin>>n;// 输入节点数// 输入每个节点的权重和子节点for(inti=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(inti=1;i<=n;i++){sum=0;// 重置总代价memset(dep,0,sizeof(dep));// 重置深度数组dfs(i,0);// 以i为根进行DFS，计算各节点深度// 计算以i为根的总代价for(intj=1;j<=n;j++)sum+=w[j]*dep[j];// 代价 = 权重 × 深度ans=min(ans,sum);// 更新最小代价}cout<<ans<<endl;// 输出结果return0;}

【运行结果】

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