RainAir
My OI Blog
RainAir
单次询问的最长瓶颈路

题目链接

题目大意

给定一个图,求瓶颈最短路(及求出一条是该路径最大值最小的路径)。

解题报告

方法一

注意最大值最小,我们立马想到了二分。

实际上,由于这道题拥挤度的范围不大,可以二分。

二分的区间就在边权最小值与最大值之间。

我们使用bfs来检查答案。每次 bfs 时验证只通过边权不超过的值来判断答案是否可行。

具体代码如下。

方法二

我们可以借助于最小生成树的思想,每次我们判断一条边的两个点是否在同一集合,如果不在就合并。

对边进行排序。只需要整体扫一遍。

具体代码如下。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/148
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

单次询问的最长瓶颈路
题目链接 题目大意 给定一个图,求瓶颈最短路(及求出一条是该路径最大值最小的路径)。 解题报告 方法一 注意最大值最小,我们立马想到了二分。 实际上,由于这道题拥挤度的范围…
扫描二维码继续阅读
2018-07-08
标签
近期评论