Kevin5307的博客

博客

PKUSC 2024 最短路径

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

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

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

此时我们得到了一个 O(qmlogm/n) 的做法。

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

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

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

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

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

评论

/cu
  • 2024-05-22 22:10:24
  • Reply
[+5]
你好
  • 2024-05-22 10:15:46
  • Reply
[+1]
/cu
  • 2024-05-28 13:26:44
  • Reply
[-48]
我声称第二部分的边数期望值是 4 倍第一部分边数。但是我没法说明我为什么没有在扯淡。
  • 2024-05-17 17:35:31
  • Reply
Comment replies
zyxawa:https://qoj.ac/images/sticker/jiehun.png

发表评论

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