NOIP2007 树网的核 [提高组]
题目:树网的核
网址:https://www.luogu.com.cn/problem/P1099
题目描述
设 T=(V,E,W)T=(V,E,W) 是一个无圈且连通的无向图(也称为无根树),每条边到有正整数的权,我们称 TT 为树网(treenetwork),其中 VV,EE 分别表示结点与边的集合,WW 表示各边长度的集合,并设 TT 有 nn 个结点。
路径:树网中任何两结点 aa,bb 都存在唯一的一条简单路径,用 d(a, b)d(a,b) 表示以 a, ba,b 为端点的路径的长度,它是该路径上各边长度之和。我们称 d(a, b)d(a,b) 为 a, ba,b 两结点间的距离。
D(v, P)=\min{d(v, u)}D(v,P)=min{d(v,u)}, uu 为路径 PP 上的结点。
树网的直径:树网中最长的路径成为树网的直径。对于给定的树网 TT,直径不一定是唯一的,但可以证明:各直径的中点(不一定恰好是某个结点,可能在某条边的内部)是唯一的,我们称该点为树网的中心。
偏心距 \mathrm{ECC}(F)ECC(F):树网 TT 中距路径 FF 最远的结点到路径 FF 的距离,即
\mathrm{ECC}(F)=\max{d(v, F),v \in V}ECC(F)=max{d(v,F),v∈V}
任务:对于给定的树网 \(T=(V, E, W)\) 和非负整数 \(s\),求一个路径 \(F\),他是某直径上的一段路径(该路径两端均为树网中的结点),其长度不超过 \(s\)(可以等于 \(s\)),使偏心距 \(ECC(F)\) 最小。我们称这个路径为树网 \(T=(V, E, W)\) 的核(Core)。必要时,\(F\) 可以退化为某个结点。一般来说,在上述定义下,核不一定只有一个,但最小偏心距是唯一的。
下面的图给出了树网的一个实例。图中,\(A-B\) 与 \(A-C\) 是两条直径,长度均为 \(20\)。点 \(W\) 是树网的中心,\(EF\) 边的长度为 \(5\)。如果指定 \(s=11\),则树网的核为路径\(DEFG\)(也可以取为路径\(DEF\)),偏心距为 \(8\)。如果指定\(s=0\)(或 \(s=1\)、\(s=2\)),则树网的核为结点 \(F\),偏心距为 \(12\)。
输入格式
共 \(n\) 行。
第 \(1\) 行,两个正整数 \(n\) 和 \(s\),中间用一个空格隔开。其中 \(n\) 为树网结点的个数,\(s\) 为树网的核的长度的上界。设结点编号以此为 \(1,2\dots,n\)。
从第 \(2\) 行到第 \(n\) 行,每行给出 \(3\) 个用空格隔开的正整数 \(u, v, w\),依次表示每一条边的两个端点编号和长度。例如,\(2 4 7\) 表示连接结点 \(2\) 与 \(4\) 的边的长度为 \(7\)。
输出格式
一个非负整数,为指定意义下的最小偏心距。
输入输出样例
输入 #1
5 2
1 2 5
2 3 2
2 4 4
2 5 3
输出 #1
5
输入 #2
8 6
1 3 2
2 3 2
3 4 6
4 5 3
4 6 4
4 7 2
7 8 3
输出 #2
5
说明/提示
- 对于 \(40\%\) 的数据,保证 \(n \le 15\)。
- 对于 \(70\%\) 的数据,保证 \(n \le 80\)。
- 对于 \(100\%\) 的数据,保证 \(n \le 300\),\(0\le s\le10^3\),\(1 \leq u, v \leq n\),\(1 \leq w \leq 10^3\)。
C ++ AC代码
总结回顾
参考文献
- 《算法竞赛进阶指南》
- https://blog.csdn.net/bjfu170203101/article/details/106337107/
- https://www.cnblogs.com/shenben/p/5895325.html
最新文章
- Vertica集群单节点宕机恢复方法
- Java_Swing程序设计_尝试开发一个登陆窗体,包括用户名、密码以及提交按钮和重置按钮,当用户输入用户名my,密码love时,弹出登陆成功提示对话框。
- Sensor信号输出YUV、RGB、RAW DATA、JPEG【转】
- flash bulider 生成app无法安装在xcode模拟器上
- ZBar之自定义二维码扫描
- c#键盘鼠标钩子
- WPF中利用后台代码实现窗口分栏动态改变
- 关于JFace带复选框的树
- dispatch_once认识分析
- 消息队列NetMQ 原理分析5-StreamEngine、Encord和Decord
- AngularJS 1.3中的一次性数据绑定(one-time bindings)
- js如何获取隐藏的元素的高度
- C语言实现二叉树的创建&;遍历
- C语言中的一维数组
- 【转】Visual Studio——多字节编码与Unicode码
- Ubuntu下安装、激活并配置Pycharm
- 假如想要建设一个能承受500万PV/每天的网站,服务器每秒要处理多少个请求才能应对?
- office 2013母版保存并调用
- mark DOwm
- python爬虫-爬取盗墓笔记
热门文章
- Nginx安全优化与性能调优
- 关于SignalR 进行双向多步对话
- 【vagrant】第一次安装添加box报错:The box failed to unpackage properly....
- 线程_gevent自动切换CPU协程
- HTML中div嵌套div的margin不起作用
- PHP 实例 - AJAX 与 XML-AJAX XML 实例
- PHP fwrite() 函数
- C/C++编程笔记:C语言贪吃蛇源代码控制台(二),分数和食物!
- centos7与centos6命令差异
- Django自学教程PDF高清电子书百度云网盘免费领取