(四五年以前的老草稿,作为强迫症还是发布出来吧)
- NOIP2012的参赛者LG异想天开打算修建一条磁悬浮列车的通道连接现代OI王国的首都(编号为1)和AY的家(编号为n).
- 当然了,
- 现代OI集团的n(1 <= n <= 1000)座城市之间没有任何的磁悬浮通道,
- 而LG通过实地勘测发现,
- 一共有p(1 <= P <= 10000)对城市之间可以建磁悬浮通道.
- 在这p对城市之中,
- 第i对城市分别为ai,
- bi,它们间的距离为li(1 <= li <= 1000000).数据中保证每对 {
- ai,
- bi
- }最多只出现1次.
- 现代OI集团决定免费帮LG修建最多k条线路的磁悬浮通道,
- 而LG要花的钱,
- 是他自己负责修建的那些线路的最长的那条路的长度.
- LG当然想花最少的钱......他想知道他最少能花多少钱.
- 第1行: 3个用空格隔开的整数: n,
- p,
- 以及k
- 第2..p + 1行: 第i + 1行为3个用空格隔开的整数: ai,
- bi,
- li
- 5 7 1
- 1 2 5
- 3 1 4
- 2 4 8
- 3 2 3
- 5 2 9
- 3 4 7
- 4 5 6
- 现代OI集团一共有5个城市.城市1不能直接与城市4,
- 5相连.城市5不能直接与城市1,
- 3相连.其余所有城市间均可修建轨道.现代OI集团可以免费为LG修建一条线路.
- 输出1个整数,
- 为LG在这项工程上的最小支出.如果任务不可能完成,
- 输出 - 1
- 4
LG 选择如下的修建方案: 1->3,3->2,2->5, 这 3 条路线的长度分别为 4,3,9.LG 让现代 OI 集团免费修建那条长度为 9 的路线, 于是, 他所需要花费的钱为 4.
这道题要做出来就必须审清题意,第一,题目要解的是需要 LG 自费的路段中最大的权值,而非路径权值和;第二,现代 OI 集团会使 K 个路段的权值归零,显然,最优解要求那免费修的 K 个路段必须是路径中权值最大的 K 个。这意味着不能再单纯地求最短路,因为最终答案选定的那条路径在免费修 K 条路段之前也许并不是该图中的最短路。
这时,我们完全可以假设编号为 i 的某路段权值就是答案,也就是把编号为 i 的路段作为 LG 自费的最长路段。如果将所有路段以长度有小到大排序,我们就可以用二分思想找到 i 的值。
来源: http://www.bubuko.com/infodetail-1950083.html