当前位置: 首页 > 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_…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

通过 Ansible 在 Windows 2022 上安装 IIS Web 服务器

拓扑结构 这是一个用于通过 Ansible 部署 IIS Web 服务器的实验室拓扑。 前提条件&#xff1a; 在被管理的节点上安装WinRm 准备一张自签名的证书 开放防火墙入站tcp 5985 5986端口 准备自签名证书 PS C:\Users\azureuser> $cert New-SelfSignedCertificate -DnsName &…...

Java中HashMap底层原理深度解析:从数据结构到红黑树优化

一、HashMap概述与核心特性 HashMap作为Java集合框架中最常用的数据结构之一&#xff0c;是基于哈希表的Map接口非同步实现。它允许使用null键和null值&#xff08;但只能有一个null键&#xff09;&#xff0c;并且不保证映射顺序的恒久不变。与Hashtable相比&#xff0c;Hash…...

【阅读笔记】MemOS: 大语言模型内存增强生成操作系统

核心速览 研究背景 ​​研究问题​​&#xff1a;这篇文章要解决的问题是当前大型语言模型&#xff08;LLMs&#xff09;在处理内存方面的局限性。LLMs虽然在语言感知和生成方面表现出色&#xff0c;但缺乏统一的、结构化的内存架构。现有的方法如检索增强生成&#xff08;RA…...

使用homeassistant 插件将tasmota 接入到米家

我写一个一个 将本地tasmoat的的设备同通过ha集成到小爱同学的功能&#xff0c;利用了巴法接入小爱的功能&#xff0c;将本地mqtt转发给巴法以实现小爱控制的功能&#xff0c;前提条件。1需要tasmota 设备&#xff0c; 2.在本地搭建了mqtt服务可&#xff0c; 3.搭建了ha 4.在h…...

Unity-ECS详解

今天我们来了解Unity最先进的技术——ECS架构&#xff08;EntityComponentSystem&#xff09;。 Unity官方下有源码&#xff0c;我们下载源码后来学习。 ECS 与OOP&#xff08;Object-Oriented Programming&#xff09;对应&#xff0c;ECS是一种完全不同的编程范式与数据架构…...

C++ 变量和基本类型

1、变量的声明和定义 1.1、变量声明规定了变量的类型和名字。定义初次之外&#xff0c;还申请存储空间&#xff0c;也可能会为变量赋一个初始值。 如果想声明一个变量而非定义它&#xff0c;就在变量名前添加关键字extern&#xff0c;而且不要显式地初始化变量&#xff1a; e…...