algorithm - 图论 : Queries with bounded edge weight in undirected graph

Question

给定 n <= 200000 的带权无向图节点和 m <= 200000边缘。边权重(整数)可以达到 1e9 .有q <= 200000查询。每个查询给出两个节点 u v和一个整数边界 p (<= 1e9) .如果u之间有路径和 v这样路径中的每条边权重都是 <= p那么答案是yes否则 no .

请注意，路径不一定是最短的。路径上的最大权重是 <= p .天真的方法当然行不通。如何快速回答查询(在 O(n lg n) 或类似的情况下)？

Answer 1

您描述的问题被称为:最宽路径问题，您可以在这里找到它:https://en.wikipedia.org/wiki/Widest_path_problem .
可以很容易地证明，对于每个 u,v 而言，具有最小最大成本的 u,v 之间的路径等于最小生成树。因此，您需要找到最小生成树，以确保已将最大生成树最小化两个顶点 u,v 之间每条路径的成本。
困难的部分是为每个查询决定从 u 到 v 的路径的最大成本是否小于或等于 p。

• 最好的方法是使用笛卡尔树(在链接的维基百科中描述)，这将允许您在恒定时间内回答每个查询，我认为构建笛卡尔树的时间复杂度为 O(nlogn)，因此总体 O(nlogn + q).但是这种方式很难实现。

• 我认为您正在寻找的是在找到最小生成树后，使用最低公共(public)祖先算法在 logn 中回答每个查询。因此找到最小生成树 (O(E log E)) 和使用具有一些预处理的最低公共(public)祖先，以便能够在 O(log n) 中回答每个查询，因此总体 O( qlogn + ElogE)。可以在此处找到最低公共(public)祖先和预处理的一种非常好的方法:https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/上面的文章很好地描述了所有的解决方案，并提供了足够的帮助代码来解决您的问题。