洛谷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_…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: 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)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...

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

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

Java中HashMap底层原理深度解析:从数据结构到红黑树优化
一、HashMap概述与核心特性 HashMap作为Java集合框架中最常用的数据结构之一,是基于哈希表的Map接口非同步实现。它允许使用null键和null值(但只能有一个null键),并且不保证映射顺序的恒久不变。与Hashtable相比,Hash…...

【阅读笔记】MemOS: 大语言模型内存增强生成操作系统
核心速览 研究背景 研究问题:这篇文章要解决的问题是当前大型语言模型(LLMs)在处理内存方面的局限性。LLMs虽然在语言感知和生成方面表现出色,但缺乏统一的、结构化的内存架构。现有的方法如检索增强生成(RA…...

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

Unity-ECS详解
今天我们来了解Unity最先进的技术——ECS架构(EntityComponentSystem)。 Unity官方下有源码,我们下载源码后来学习。 ECS 与OOP(Object-Oriented Programming)对应,ECS是一种完全不同的编程范式与数据架构…...
C++ 变量和基本类型
1、变量的声明和定义 1.1、变量声明规定了变量的类型和名字。定义初次之外,还申请存储空间,也可能会为变量赋一个初始值。 如果想声明一个变量而非定义它,就在变量名前添加关键字extern,而且不要显式地初始化变量: e…...