当前位置: 首页 > news >正文

洛谷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 1n100 0 ≤ u , v ≤ n 0 \leq u, v \leq n 0u,vn 1 ≤ w ≤ 1 0 5 1 \leq w \leq 10^5 1w105

//【参考代码】
#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 医院设置 题目描述 设有一棵二叉树&#xff0c;如图&#xff1a; 其中&#xff0c;圈中的数字表示结点中居民的人口。圈边上数字表示结点编号&#xff0c;现在要求在某个结点上建立一个医院&#xff0c;使所有居民所走的路程之和为最小&#xff0c;同时约定&#xff0c…...

哈希表的理解和实现

目录 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)

分治算法&#xff08;Divide-and-Conquer Algorithm&#xff09;是一种重要的计算机科学和数学领域的通用问题解决策略。其基本思想是将一个复杂的大规模问题分割成若干个规模较小、结构与原问题相似但相对简单的子问题来处理。这些子问题相互独立&#xff0c;分别求解后再通过…...

Java项目:基于ssm框架实现的实验室耗材管理系统(B/S架构+源码+数据库+毕业论文+答辩PPT)

一、项目简介 本项目是一套基于ssm框架实现的实验室耗材管理系统 包含&#xff1a;项目源码、数据库脚本等&#xff0c;该项目附带全部源码可作为毕设使用。 项目都经过严格调试&#xff0c;eclipse或者idea 确保可以运行&#xff01; 二、技术实现 jdk版本&#xff1a;1.8 …...

如何通过专业的二手机店erp优化手机商家运营!

在数字化浪潮席卷全球的大背景下&#xff0c;手机行业作为科技发展的前沿阵地&#xff0c;正经历着前所未有的变革。对于众多手机商家而言&#xff0c;如何在这场变革中抢占先机&#xff0c;实现数字化转型&#xff0c;成为了摆在他们面前的一大难题。幸运的是&#xff0c;途渡…...

CentOS常见的命令及其高质量应用

CentOS是一个流行的、基于Red Hat Enterprise Linux&#xff08;RHEL&#xff09;的开源服务器操作系统。由于其稳定性和强大的性能&#xff0c;CentOS被广泛应用于各种服务器环境中。为了有效地管理和维护CentOS系统&#xff0c;熟悉并掌握其常见命令是非常重要的。本文将介绍…...

nodeJs用ffmpeg直播推流到rtmp服务器上

总结 最近在写直播项目 目前比较重要的点就是推拉流 自己也去了解了一下 ffmpeg FFmpeg 是一个开源项目&#xff0c;它提供了一个跨平台的命令行工具&#xff0c;以及一系列用于处理音频和视频数据的库。FFmpeg 能够执行多种任务&#xff0c;包括解封装、转封装、视频和音频…...

Django信号与扩展:深入理解与实践

title: Django信号与扩展&#xff1a;深入理解与实践 date: 2024/5/15 22:40:52 updated: 2024/5/15 22:40:52 categories: 后端开发 tags: Django信号松耦合观察者扩展安全性能 第一部分&#xff1a;Django信号基础 Django信号概述 一. Django信号的定义与作用 Django信…...

使用Docker创建verdaccio私服

verdaccio官网 1.Docker安装 这边以Ubuntu安装为例Ubuntu 安装Docker​&#xff0c;具体安装方式请根据自己电脑自行搜索。 2.下载verdaccio docker pull verdaccio/verdaccio3.运行verdaccio 运行容器&#xff1a; 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;--如果替换字符整个为空字符 &#xff0c;则直接返回null select translate(abc你好cdefgdc,abcdefg,122)from dual; sel…...

算法-卡尔曼滤波之卡尔曼滤波的第二个方程:预测方程(状态外推方程)

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

刘邦的创业团队是沛县人,朱元璋的则是凤阳;要创业,一个县人才就够了

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

【Unity之FairyGUI】你了解FGUI吗,跨平台多功能高效UI插件

&#x1f468;‍&#x1f4bb;个人主页&#xff1a;元宇宙-秩沅 &#x1f468;‍&#x1f4bb; hallo 欢迎 点赞&#x1f44d; 收藏⭐ 留言&#x1f4dd; 加关注✅! &#x1f468;‍&#x1f4bb; 本文由 秩沅 原创 &#x1f468;‍&#x1f4bb; 收录于专栏&#xff1a;就业…...

基于51单片机的自动浇花器电路

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

2024中国(重庆)商旅文化川渝美食暨消费品博览会8月举办

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

MacOS docker 安装与配置

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

【嵌入式大赛应用赛道】机械手臂

电机 进步电机&#xff1a;它的转动是以确定的步数进行的&#xff0c;只要计算好脉冲数量和频率&#xff0c;就可以准确预测和控制电机的转动角度、速度以及停止的位置 伺服电机&#xff1a;将输入的电信号&#xff08;如电压或电流指令&#xff09;转换成轴上的精确旋转运动…...

MES系统主要包括那些功能?

一开始接触MES系统&#xff0c;对MES细条的功能不清楚&#xff0c;这样很正常&#xff0c;因为MES系统相对于其他系统来讲&#xff0c;功能有多又复杂! 作为曾参与200企业MES系统架构的资深从业人员&#xff0c;我给大家选出了一款优秀模板——简道云MES系统&#xff0c;给大家…...

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 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 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代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

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 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

Springboot社区养老保险系统小程序

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

关于easyexcel动态下拉选问题处理

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