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

题目链接

题目大意

给出一个由 $ n $个点 $ m $条边的图,现有$ q $组询问,每次需要你求出从$ x $到$ y $的一条简单路径,使路径上所有边中最小值最大,并输出这个最大值。

若不存在这样的路径,则输出$ −1 $。

解题报告

做这一道题之前,建议先看一下单次询问的最长瓶颈路这道题目。

注意解法二:我们最后的答案其实就在最小生成树上。

即我们可以证明:无向图中最小生成树中u到v的路径一定是u到v的最小瓶颈路之一。

同理:无向图中最大生成树中u到v的路径一定是u到v的最大瓶颈路之一。

所以说,对于这一道题,我们对这个无向图预先进行求最大生成树,然后这道题就成功的转化为求u到v的路径上的最小值。我们可以用LCA解决。

具体来说是我们在对f数组进行预处理时,维护一个从该节点向上跳2^k的父亲中经过的所有边的最小值。

查询?只需要在同时跳 $ u $ 和 $v$ 的时候,顺便更新最小值即可。个人感觉思想类似于树链剖分中的查询操作。

样例代码

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/147
如文中无特殊声明,本文采用 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

多次询问的最长瓶颈路
题目链接 题目大意 给出一个由 $ n $个点 $ m $条边的图,现有$ q $组询问,每次需要你求出从$ x $到$ y $的一条简单路径,使路径上所有边中最小值最大,并输出这个最大值。 若不存在…
扫描二维码继续阅读
2018-07-10
标签
近期评论