计算无向图中节点对数，使得W - L >= K

Question

计算无向图中节点对数，使得W - L >= K

algorithmgraph-theoryundirected-graph

9

问题：

给定一个有N个节点和N-1条边的无向图。所有边的长度都为1。每条边i有一个权重Wi。(0 ≤ Wi ≤ 10.000)

保证该图没有任何环。因此，两个节点之间始终存在一条（仅有的）最短路径。

从图中选择一对节点(u, v)：

l是2个节点之间最短路径的长度
w是2个节点之间最短路径上具有最大权重的边

给定数字K，请计算图中有多少对(u, v)满足w - l ≥ K。

示例：

N = 3, K = 1
Edges:
1 - 2 - 3
1 - 3 - 2

（边被描述为：u-v-w）

答案：6。所有可能的对为：(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)

暴力解决方案（N <100）：

遍历所有(u,v)的对，找到沿着w和l的最短路径。如果w-l>=K，则增加答案。

时间复杂度：O（N^3）

P / S： 我尝试并成功使用暴力解决方案（N <100）。但我正在努力寻找适用于高达100,000的解决方案。

- unglinh279

2

“最短路径中的最大权重”是什么意思？它是路径中具有最高权重的边还是总路径成本，比较两个节点之间不同的最短路径？如果u和v之间存在两条不同的最短路径，其最大单边权重不同怎么办？是否假定只存在一条从u到v的最短路径？ - גלעד ברקן

1

“在两个节点之间的最短路径中的最大权重”是路径中具有最高权重的边。对于每一对(u, v)节点，只有一条最短路径。 - unglinh279

这个东西在线上有测试的地方吗？ - no comment

3

提示：质心分解应该在O（n log²(n)）的时间复杂度内工作。 - user202729

1

你的图是一棵树（无环，n个节点，n-1条边），因此任意两个节点之间只有一条路径。 - Dave

显示剩余4条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

为了解决用户202729的提示问题：

1. 找到质心（移除该点后，剩下的子树中每个顶点数量都不超过整棵树节点数量的一半）。 2. 计算路径包含质心的点对(u, v)的数量。 3. 删除质心，在每个子树上递归操作。

步骤1是O(n)（有一个标准算法），步骤2将是O(n log n)，因此主定理给出整体的时间复杂度为O(n log^2 n)。

为了实现步骤2，在质心处将树变成有根树，并计算出质心以及每个子节点的各个深度的后代数量。将结果放入Fenwick树中，以获得O(log n)时间的前缀和查询。

现在，按权值对边进行排序。从最重的边e开始，向轻的方向遍历，计算其路径上的点对数量。边e连接父级和子级；让x是孩子。对于x的每个（包括x）后代u，让ℓ * = w - K是最大的ℓ，使得w-ℓ≥K。用两个前缀和计算深度至多ℓ * - depth(u)的其他子树中的顶点v的数量。然后向Fenwick树发出更新，以从计数中删除u。