sol - 0x63
注意到K只能是1或2,也就是说只能建0/1/2条新道路
我们分类讨论
当修建0条新道路的时候,
执行遍历会恰好遍历到每条边2次,答案为2*(n-1)
当修建1条新道路的时候,
我们设新道路连接x,y,则本来需要走两次的边(x,y)只要走一次,得到结果是2*(n-1)-(x,y),
易得(x,y)取直径L1时值最小,为2*(n-1)-L1+1
当修建2条新道路的时候,
就相当于在修建一条新道路的基础上在修建1条新道路
如果新道路形成的环有一部分与旧道路形成的环重叠,
那么我们必须再次经过这些边
否则答案继续减小
我们把原直径上的边权取反,然后再次求直径L2,答案就是2*(n-1)-L1+1-L2+1
转自《算法竞赛进阶指南》
解法1:暴力
直接找出直径后枚举左右端点,O(n3)
解法2:暴力的优化!QAQ
直接枚举左端点,让右端点最远,O(n2),可轻松AC原题
解法3:二分
为了通过加强版,我们继续观察:发现本题答案具有单调性,珂以二分答案
那么问题就转化为“验证是否存在一个核的偏心距不超过mid”
珂以找距直径两端点距离分别小于等于mid的两个点作为树网的核
珂以O(N)判定是否超过S ;
解法4:分析性质
设直径上的点为u1,u2......ut,先把这些节点标记为已访问,通过深度优先遍历求出d[ui]表示不经过直径上的点能到达的最远点的距离
以ui,uj为端点的点的树网的核的偏心距为max(max{d{uk|i≤k≤j},dist(u1,ui) ,dist(uj,ut)) ;
此时单调队列维护d[uk]就珂以做到O(N)了!
Warning!
本文由 TYQ 创作,采用 知识共享署名 4.0 国际许可协议进行许可。
转载要与作者联系,并需在正文明显处署名作者且注明文章出处。
对了,我永远喜欢C++啊。
最新文章
- ascii、unicode、utf、gb等编码详解
- Redis基础命令
- Java 线程综述
- strong和b
- 《PHP和MySQL Web开发》精彩的地方收录
- PHP使用SwiftMailer发送邮件
- 关于MATLAB中的tic toc的问题
- Windows 7下解决: java.net.SocketException: No buffer space available (maximum connections reached?)
- SVN分支/合并操作小记
- 【深度学习】批归一化(Batch Normalization)
- UOJ#75. 【UR #6】智商锁 随机化算法 矩阵树定理
- select样式设计
- CRM 2013 批量更新two options的缺省值
- J S 脚本语言 if() { if { } else { } } var a =100; switch { case ( ) break ; } 基础详解 , 最下面有例子
- [转]Magento2命令行配置之性能测试生成数据
- ubuntu 中DNAT SNAT配置实验.
- 库、教程、论文实现,这是一份超全的PyTorch资源列表(Github 2.2K星)
- 2018.09.12 earthquake(最优比率生成树)
- 【JavaScript 从零开始】表达式和运算符(2)
- Hello World with Ant
热门文章
- Tornado的XSRF防范
- (转)null和NULL和nullptr和””区别
- EUI库 - 9 - 数据集合 - 列表
- Egret Engine 2D - 项目配置
- Spring Boot2(001):入门介绍和一些官网链接参考
- org.apache.jasper.JasperException: /WEB-INFO/jsp/product/edit.jsp(168,45)
- cf 444C.
- 四、CI框架之通过URL路径访问C中的函数
- SASS - @extend(继承)指令
- SASS - 使用Sass程序