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

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

css实现圆环展示百分比,根据值动态展示所占比例

代码如下 <view class""><view class"circle-chart"><view v-if"!!num" class"pie-item" :style"{background: conic-gradient(var(--one-color) 0%,#E9E6F1 ${num}%),}"></view><view v-else …...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中&#xff0c;具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类&#xff1a; 身份验证机制&#xff1a;直接将未经授权的爬虫阻挡在外反爬技术体系&#xff1a;通过各种技术手段增加爬虫获取数据的难度…...

【git】把本地更改提交远程新分支feature_g

创建并切换新分支 git checkout -b feature_g 添加并提交更改 git add . git commit -m “实现图片上传功能” 推送到远程 git push -u origin feature_g...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...