洛谷P1364 医院设置
P1364 医院设置
题目描述
设有一棵二叉树,如图:
其中,圈中的数字表示结点中居民的人口。圈边上数字表示结点编号,现在要求在某个结点上建立一个医院,使所有居民所走的路程之和为最小,同时约定,相邻接点之间的距离为 1 1 1。如上图中,若医院建在 1 1 1 处,则距离和 = 4 + 12 + 2 × 20 + 2 × 40 = 136 =4+12+2\times20+2\times40=136 =4+12+2×20+2×40=136;若医院建在 3 3 3 处,则距离和 = 4 × 2 + 13 + 20 + 40 = 81 =4\times2+13+20+40=81 =4×2+13+20+40=81。
输入格式
第一行一个整数 n n n,表示树的结点数。
接下来的 n n n 行每行描述了一个结点的状况,包含三个整数 w , u , v w, u, v w,u,v,其中 w w w 为居民人口数, u u u 为左链接(为 0 0 0 表示无链接), v v v 为右链接(为 0 0 0 表示无链接)。
输出格式
一个整数,表示最小距离和。
样例 #1
样例输入 #1
5
13 2 3
4 0 0
12 4 5
20 0 0
40 0 0
样例输出 #1
81
提示
数据规模与约定
对于 100 % 100\% 100% 的数据,保证 1 ≤ n ≤ 100 1 \leq n \leq 100 1≤n≤100, 0 ≤ u , v ≤ n 0 \leq u, v \leq n 0≤u,v≤n, 1 ≤ w ≤ 1 0 5 1 \leq w \leq 10^5 1≤w≤105。
//【参考代码】
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N =105;
int map[N][N];//存图的
int v[N];
int n;
int main() {memset(map,0x3f,sizeof(map));scanf("%d",&n);//存储图 for(int i=1; i<=n; i++){int left, right;scanf("%d",&v[i]);scanf("%d",&left);scanf("%d",&right);if(left!=0){map[i][left] = 1;map[left][i] = 1;}if(right!=0){map[i][right] = 1;map[right][i] = 1;}map[i][i] = 0;}//弗洛伊德 for(int k=1; k<=n; k++){for(int i=1; i<=n; i++){for(int j=1; j<=n; j++){map[i][j] = min(map[i][j], map[i][k]+map[k][j]);}}} //医院设置的计算式子int min = 1000;for(int i=1; i<=n; i++){int sum = 0;for(int j=1; j<=n; j++){sum+=map[i][j]*v[j];}if(sum<min){min = sum;}}cout<<min;return 0;
}
相关文章:

洛谷P1364 医院设置
P1364 医院设置 题目描述 设有一棵二叉树,如图: 其中,圈中的数字表示结点中居民的人口。圈边上数字表示结点编号,现在要求在某个结点上建立一个医院,使所有居民所走的路程之和为最小,同时约定,…...

哈希表的理解和实现
目录 1. 哈希的概念 (是什么) 2. 实现哈希的两种方式 (哈希函数) 2.1. 直接定址法 2.2. 除留余数法 2.2.1. 哈希冲突 3. 补充知识 3.1. 负载因子 3.2. 线性探测和二次探测 4. 闭散列实现哈希表 (开放定址法) 4.1. 开放定址法的实现框架 4.2. Xq::hash_table::insert…...
分治算法(Divide-and-Conquer Algorithm)
分治算法(Divide-and-Conquer Algorithm)是一种重要的计算机科学和数学领域的通用问题解决策略。其基本思想是将一个复杂的大规模问题分割成若干个规模较小、结构与原问题相似但相对简单的子问题来处理。这些子问题相互独立,分别求解后再通过…...

Java项目:基于ssm框架实现的实验室耗材管理系统(B/S架构+源码+数据库+毕业论文+答辩PPT)
一、项目简介 本项目是一套基于ssm框架实现的实验室耗材管理系统 包含:项目源码、数据库脚本等,该项目附带全部源码可作为毕设使用。 项目都经过严格调试,eclipse或者idea 确保可以运行! 二、技术实现 jdk版本:1.8 …...
如何通过专业的二手机店erp优化手机商家运营!
在数字化浪潮席卷全球的大背景下,手机行业作为科技发展的前沿阵地,正经历着前所未有的变革。对于众多手机商家而言,如何在这场变革中抢占先机,实现数字化转型,成为了摆在他们面前的一大难题。幸运的是,途渡…...
CentOS常见的命令及其高质量应用
CentOS是一个流行的、基于Red Hat Enterprise Linux(RHEL)的开源服务器操作系统。由于其稳定性和强大的性能,CentOS被广泛应用于各种服务器环境中。为了有效地管理和维护CentOS系统,熟悉并掌握其常见命令是非常重要的。本文将介绍…...

nodeJs用ffmpeg直播推流到rtmp服务器上
总结 最近在写直播项目 目前比较重要的点就是推拉流 自己也去了解了一下 ffmpeg FFmpeg 是一个开源项目,它提供了一个跨平台的命令行工具,以及一系列用于处理音频和视频数据的库。FFmpeg 能够执行多种任务,包括解封装、转封装、视频和音频…...
Django信号与扩展:深入理解与实践
title: Django信号与扩展:深入理解与实践 date: 2024/5/15 22:40:52 updated: 2024/5/15 22:40:52 categories: 后端开发 tags: Django信号松耦合观察者扩展安全性能 第一部分:Django信号基础 Django信号概述 一. Django信号的定义与作用 Django信…...

使用Docker创建verdaccio私服
verdaccio官网 1.Docker安装 这边以Ubuntu安装为例Ubuntu 安装Docker,具体安装方式请根据自己电脑自行搜索。 2.下载verdaccio docker pull verdaccio/verdaccio3.运行verdaccio 运行容器: docker run -it -d --name verdaccio -p 4873:4873 ver…...
Spring 使用 Groovy 实现动态server
本人在项目中遇到这么个需求,有一个模块的server方法需要频繁修改 经阅读可以使用 Groovy 使用java脚本来时pom坐标 <dependency><groupId>org.codehaus.groovy</groupId><artifactId>groovy</artifactId><version>3.0.9</version>…...
oracle不得不知道的sql
一、oracle 查询语句 1.translate select translate(abc你好cdefgdc,abcdefg,1234567)from dual; select translate(abc你好cdefgdc,abcdefg,)from dual;--如果替换字符整个为空字符 ,则直接返回null select translate(abc你好cdefgdc,abcdefg,122)from dual; sel…...

算法-卡尔曼滤波之卡尔曼滤波的第二个方程:预测方程(状态外推方程)
在上一节中,使用了静态模型,我们推导出了卡尔曼滤波的状态更新方程,但是在实际情况下,系统都是动态,预测阶段,前后时刻的状态是改变的,此时我们引入预测方程,也叫状态外推方程&#…...

刘邦的创业团队是沛县人,朱元璋的则是凤阳;要创业,一个县人才就够了
当人们回顾刘邦和朱元璋的创业经历时,总是会感慨他们起于微末,都创下了偌大王朝,成就无上荣誉。 尤其是我们查阅史书时,发现这二人的崛起班底都是各自的家乡人,例如刘邦的班底就是沛县人,朱元璋的班底是凤…...

【Unity之FairyGUI】你了解FGUI吗,跨平台多功能高效UI插件
👨💻个人主页:元宇宙-秩沅 👨💻 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 👨💻 本文由 秩沅 原创 👨💻 收录于专栏:就业…...

基于51单片机的自动浇花器电路
一、系统概述 自动浇水灌溉系统设计方案,以AT89C51单片机为控制核心,采用模块化的设计方法。 组成部分为:5V供电模块、土壤湿度传感器模块、ADC0832模数转换模块、水泵控制模块、按键输入模块、LCD显示模块和声光报警模块,结构如…...

2024中国(重庆)商旅文化川渝美食暨消费品博览会8月举办
2024中国(重庆)商旅文化川渝美食暨消费品博览会8月举办 邀请函 主办单位: 中国航空学会 重庆市南岸区人民政府 招商执行单位: 重庆港华展览有限公司 展会背景: 2024中国航空科普大会暨第八届全国青少年无人机大赛在重庆举办ÿ…...

MacOS docker 安装与配置
orbstack 安装 官网: https://orbstack.dev 下载链接:Download OrbStack Fast, light, simple Docker Desktop alternative 选择是Apple M系列处理器, 或 Intel系列处理器 到这里就安装好了Orbstack软件,下面开始配置docker 下…...

【嵌入式大赛应用赛道】机械手臂
电机 进步电机:它的转动是以确定的步数进行的,只要计算好脉冲数量和频率,就可以准确预测和控制电机的转动角度、速度以及停止的位置 伺服电机:将输入的电信号(如电压或电流指令)转换成轴上的精确旋转运动…...

MES系统主要包括那些功能?
一开始接触MES系统,对MES细条的功能不清楚,这样很正常,因为MES系统相对于其他系统来讲,功能有多又复杂! 作为曾参与200企业MES系统架构的资深从业人员,我给大家选出了一款优秀模板——简道云MES系统,给大家…...
git 合并commit
操作步骤 合并commit cd xxx/ git checkout a8c0efegfwgtw # 最新commit git reset rhgertheryhg --soft # 最初的commit git status git checkout -b test1 git commit -m "test1" git branch git push origin test1 git tag test1_v0.0.1 git push origin test1_…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
在rocky linux 9.5上在线安装 docker
前面是指南,后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

Docker 运行 Kafka 带 SASL 认证教程
Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明:server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...
django filter 统计数量 按属性去重
在Django中,如果你想要根据某个属性对查询集进行去重并统计数量,你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求: 方法1:使用annotate()和Count 假设你有一个模型Item,并且你想…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...

视频字幕质量评估的大规模细粒度基准
大家读完觉得有帮助记得关注和点赞!!! 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用,因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型(VLMs)在字幕生成方面…...

Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...

关于easyexcel动态下拉选问题处理
前些日子突然碰到一个问题,说是客户的导入文件模版想支持部分导入内容的下拉选,于是我就找了easyexcel官网寻找解决方案,并没有找到合适的方案,没办法只能自己动手并分享出来,针对Java生成Excel下拉菜单时因选项过多导…...