Kevin5307的博客

博客

PKUSC 2024 最短路径

2024-05-17 17:33:23 By Kevin5307

考虑从 $s,t$ 开始双向 Dijkstra 跑最短路,直到两边经过的点集出现公共点为止,设为 $p$。由于数据随机,所以每个点会等概率地被 $s$ 和 $t$ 增广到,由生日悖论可以得出,此时经过的点的数量是 $O(\sqrt n)$ 级别的。

考虑此时如何统计答案,容易发现会被算进答案的路径形态一定是:$s\to u\to v\to t$,其中 $u,v$ 之间直接由边相连,$u$ 和 $v$ 分别属于刚才的最短路过程中被 $s,t$ 增广到的集合。该结论证明是简单的,因为如果路径形态是 $s\to u\to x\to v\to t$,由最短路过程的性质有 $dist(s,x)\geq dist(s,p),dist(x,t)\geq dist(p,t)$,这样的路径必然是不优的。事实上需要特殊考虑 $s\to p\to t$,不过这是 trivial 的。

此时我们得到了一个 $O(qm\log m/ \sqrt n)$ 的做法。

为了优化掉复杂度中的 $m$,我们对 Dijkstra 应用一个优化:将一个点所有出边按照边权排序,在松弛时不要全部同时加入优先队列,而是当上一条边出队之后再加入下一条边。这样,第一部分的复杂度就变成了 $O(q\sqrt n\log n)$。

对于第二部分,我们枚举路径中的 $u$ 和它的出边,去更新答案,总共需要考虑 $O(m/\sqrt n)$ 条边。但是事实上,我们可以考虑在 $dist(s,u)$ 和 $dist(v,t)$ 中较小的那一侧去枚举。若 $dist(s,u)+e(u,v)+dist(v,t)\geq dist(s,p)+dist(p,t)$,那么这条路径必然不优。所以我们只需要枚举到 $e(u,v)\leq 2(\max\{dist(s,p),dist(p,t)\}-dist(s,u))$ 即可,较小的那一侧是 $t$ 那一侧的情况是对称的。

那么这一部分总共有多少条边呢?感性理解,对于 $e(u,v)\leq 2(\max\{dist(s,p),dist(p,t)\}-dist(s,u))$ 的边中,满足 $e(u,v)\leq \max\{dist(s,p),dist(p,t)\}-dist(s,u)$ 是所有在第一部分最短路过程中被处理过的边,而这两个值域恰是两倍关系,故第二部分的边数也是 $O(\sqrt n)$ 级别的。

这个感性理解事实上有潜在的漏洞,因为涉及到的概率不一定独立。钱哥声称,第二部分的边数的上界为第一部分边数乘 $O(\log n)$,那么第二部分的边数是 $O(\sqrt n\log n)$ 级别的。总时间复杂度是 $O(q\sqrt n\log n)$。

关于这个问题,钱哥有一个绝妙的证明,但是后面忘了。

评论

_map_
/cu
  • 2024-05-22 22:10:24
  • Reply
LuoTianYi
你好
  • 2024-05-22 10:15:46
  • Reply
zhaohaikun
/cu
  • 2024-05-28 13:26:44
  • Reply
Kevin5307
我声称第二部分的边数期望值是 $4$ 倍第一部分边数。但是我没法说明我为什么没有在扯淡。
  • 2024-05-17 17:35:31
  • Reply

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。