P1364 医院设置网页链接P1364 医院设置题目描述设有一棵二叉树如图其中圈中的数字表示结点中居民的人口。圈边上数字表示结点编号现在要求在某个结点上建立一个医院使所有居民所走的路程之和为最小同时约定相邻节点之间的距离为1 11。如上图中若医院建在1 11处则距离和 4 12 2 × 20 2 × 40 136 4122\times202\times401364122×202×40136若医院建在3 33处则距离和 4 × 2 13 20 40 81 4\times2132040814×213204081。输入格式第一行一个整数n nn表示树的结点数。接下来的n nn行每行描述了一个结点的状况包含三个整数w , u , v w, u, vw,u,v其中w ww为居民人口数u uu为左链接为0 00表示无链接v vv为右链接为0 00表示无链接。输出格式一个整数表示最小距离和。输入输出样例 #1输入 #15 13 2 3 4 0 0 12 4 5 20 0 0 40 0 0输出 #181说明/提示数据规模与约定对于100 % 100\%100%的数据保证1 ≤ n ≤ 100 1 \leq n \leq 1001≤n≤1000 ≤ u , v ≤ n 0 \leq u, v \leq n0≤u,v≤n1 ≤ w ≤ 10 5 1 \leq w \leq 10^51≤w≤105。解题思路本题本质是树的带权重心求解目标是找到一个节点使得所有节点的权值与到该节点距离的乘积之和最小。由于节点数量n ≤ 100 n \le 100n≤100数据规模极小采用暴力枚举 BFS求最短路径的方案即可高效通过实现简单且不易出错。算法核心逻辑建图存储将二叉树视为无向图每个节点与它的左右孩子之间建立双向边使用邻接矩阵存储连接关系。枚举医院位置依次将每个节点作为医院的候选位置计算该位置下的总路程和。BFS计算距离和对于每个候选起点通过广度优先搜索遍历整棵树逐层计算各节点到起点的距离同时累加「节点人口数 × 距离」得到总路程和。更新最小值遍历所有候选节点后最小的总路程和即为答案。因为树是无权连通图BFS可以天然得到节点间的最短距离单次BFS时间复杂度为O ( n ) O(n)O(n)总时间复杂度为O ( n 2 ) O(n^2)O(n2)完全适配题目数据约束。总结核心逻辑暴力枚举所有可能的医院选址通过BFS计算每个选址的带权总距离取最小值作为结果。关键操作邻接矩阵建树、BFS层序遍历求距离、带权距离累加、全局最小值更新。效率保障节点数量少平方级复杂度无运行压力代码直观易写不易出错。代码简要说明全局数组定义g为邻接矩阵存储节点连接关系v为BFS访问标记数组num存储每个节点的居民人口数ans初始化极大值用于记录最小总距离。BFS函数接收起点编号初始化访问标记与队列从起点开始层序遍历每访问一个相邻节点累加其人口数乘以当前距离标记访问后将其入队最终返回总带权距离和。主函数建图读取节点数n逐行读取每个节点的人口数与左右孩子编号若孩子非0则在邻接矩阵中标记双向边。枚举求解循环枚举每个节点作为医院起点调用BFS计算总距离更新全局最小值ans最后输出结果。类型安全全程使用long long存储距离和避免大数相乘导致的整数溢出。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;boolg[105][105]{0};boolv[105]{0};ll n,num[105],ans1LL30;structnode{ll u,step;};llbfs(ll x){memset(v,0,sizeof(v));queuenodeq;v[x]1;q.push((node){x,0});ll sum0;while(!q.empty()){node nowq.front();q.pop();for(ll i1;in;i)if(g[now.u][i]!v[i]){node next{i,now.step1};sumnum[i]*next.step;v[i]1;q.push(next);}}returnsum;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinn;for(ll i1;in;i){ll a,l,r;cinalr;num[i]a;if(l)g[i][l]g[l][i]1;if(r)g[i][r]g[r][i]1;}for(ll i1;in;i)ansmin(ans,bfs(i));coutansendl;return0;}
P1364 医院设置【洛谷算法习题】
P1364 医院设置网页链接P1364 医院设置题目描述设有一棵二叉树如图其中圈中的数字表示结点中居民的人口。圈边上数字表示结点编号现在要求在某个结点上建立一个医院使所有居民所走的路程之和为最小同时约定相邻节点之间的距离为1 11。如上图中若医院建在1 11处则距离和 4 12 2 × 20 2 × 40 136 4122\times202\times401364122×202×40136若医院建在3 33处则距离和 4 × 2 13 20 40 81 4\times2132040814×213204081。输入格式第一行一个整数n nn表示树的结点数。接下来的n nn行每行描述了一个结点的状况包含三个整数w , u , v w, u, vw,u,v其中w ww为居民人口数u uu为左链接为0 00表示无链接v vv为右链接为0 00表示无链接。输出格式一个整数表示最小距离和。输入输出样例 #1输入 #15 13 2 3 4 0 0 12 4 5 20 0 0 40 0 0输出 #181说明/提示数据规模与约定对于100 % 100\%100%的数据保证1 ≤ n ≤ 100 1 \leq n \leq 1001≤n≤1000 ≤ u , v ≤ n 0 \leq u, v \leq n0≤u,v≤n1 ≤ w ≤ 10 5 1 \leq w \leq 10^51≤w≤105。解题思路本题本质是树的带权重心求解目标是找到一个节点使得所有节点的权值与到该节点距离的乘积之和最小。由于节点数量n ≤ 100 n \le 100n≤100数据规模极小采用暴力枚举 BFS求最短路径的方案即可高效通过实现简单且不易出错。算法核心逻辑建图存储将二叉树视为无向图每个节点与它的左右孩子之间建立双向边使用邻接矩阵存储连接关系。枚举医院位置依次将每个节点作为医院的候选位置计算该位置下的总路程和。BFS计算距离和对于每个候选起点通过广度优先搜索遍历整棵树逐层计算各节点到起点的距离同时累加「节点人口数 × 距离」得到总路程和。更新最小值遍历所有候选节点后最小的总路程和即为答案。因为树是无权连通图BFS可以天然得到节点间的最短距离单次BFS时间复杂度为O ( n ) O(n)O(n)总时间复杂度为O ( n 2 ) O(n^2)O(n2)完全适配题目数据约束。总结核心逻辑暴力枚举所有可能的医院选址通过BFS计算每个选址的带权总距离取最小值作为结果。关键操作邻接矩阵建树、BFS层序遍历求距离、带权距离累加、全局最小值更新。效率保障节点数量少平方级复杂度无运行压力代码直观易写不易出错。代码简要说明全局数组定义g为邻接矩阵存储节点连接关系v为BFS访问标记数组num存储每个节点的居民人口数ans初始化极大值用于记录最小总距离。BFS函数接收起点编号初始化访问标记与队列从起点开始层序遍历每访问一个相邻节点累加其人口数乘以当前距离标记访问后将其入队最终返回总带权距离和。主函数建图读取节点数n逐行读取每个节点的人口数与左右孩子编号若孩子非0则在邻接矩阵中标记双向边。枚举求解循环枚举每个节点作为医院起点调用BFS计算总距离更新全局最小值ans最后输出结果。类型安全全程使用long long存储距离和避免大数相乘导致的整数溢出。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;boolg[105][105]{0};boolv[105]{0};ll n,num[105],ans1LL30;structnode{ll u,step;};llbfs(ll x){memset(v,0,sizeof(v));queuenodeq;v[x]1;q.push((node){x,0});ll sum0;while(!q.empty()){node nowq.front();q.pop();for(ll i1;in;i)if(g[now.u][i]!v[i]){node next{i,now.step1};sumnum[i]*next.step;v[i]1;q.push(next);}}returnsum;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinn;for(ll i1;in;i){ll a,l,r;cinalr;num[i]a;if(l)g[i][l]g[l][i]1;if(r)g[i][r]g[r][i]1;}for(ll i1;in;i)ansmin(ans,bfs(i));coutansendl;return0;}
