P2483 【模板】k短路 / [SDOI2010]魔法猪学院

· · 题解

前言

鉴于此题有更优秀复杂度的可并堆做法但未被题解给出，故在此补充一下。

本文重点在于可并堆如何优化的细节上，一般的可持久化可并堆请参考其他题解。

正文

分部分来考虑复杂度：

  1. 建反图跑最短路树：

    如果你使用了普通堆优化的 Dijkstra，恭喜你，你的复杂度已经为 O(m\log{m})，没必要进行后面的优化了。

    于是我们需要使用广为人知且不难科技：斐波那契堆优化 Dijkstra，可以轻松做到 O(m+n\log{n})。戳我看蒟蒻的Fib堆优化Dij

  2. 可持久化可并堆

    一般的可持久化可并堆将 m 条边都插入了进去，复杂度显然 O(m\log{m})，看似没有优化的空间。

    但我们发现，建可持久化可并堆时，对于每个点，每次会将自己连出去的所有非树边并入可并堆，我们将最短路树上的 n 个点用 m\log{m} 的代价并起来显然血亏。

    如果我们将每个点的边提前建一个堆，每次只丢一个堆顶进去不就只有 n\log{n} 了嘛。只要我们动用一点小小的黑科技：O(n) 建大小为 n 的二叉堆，在这里我们就可以做到 O(m+n\log{n})。

    先来看 O(n) 建堆，简单来说，原理就是从下往上将每个点不停向下换，冷静分析复杂度可以发现是 O(n) 的。

    再说可持久化堆，其实是可持久化可并堆套堆(形象吧)，因为它外层是可持久化可并堆，内层还有一个堆。它们以堆顶相关联，故堆顶既是外层堆节点，又是内层堆堆顶。

    原来堆的意义是一个节点及后继节点的所有非树边，而现在外层堆是一个节点及后继节点的非树边堆顶，一个内层堆的节点及堆顶都代表一条边。

    这里实际上利用了每个点非树出边都是相同的性质提前建堆进行了优化。

  3. K 短路：

    原来我们选择堆中一个节点的儿子，代表用一个更大的后继非树边(名词可能不严谨)替代它。

    而现在我们可以选择从一个堆顶(也即外层节点)往内层堆的儿子里走，代表用这个节点连出的更大非树边，或是选择外层堆的儿子，代表用更大的后继节点的边来代替。

    如果不是替换而是加新边就和一般做法一样丢入下一个点的堆顶即可，注意这里是外层堆顶。

    时间仍为 O(k\log{k})，因为每次出堆必定代表一条路，而入堆的只是其二叉堆的儿子，可以忽略不大的常数。

故我们整体上可以实现 O(n\log{n}+m+k\log{k}) 的复杂度通过此题，相较于一般算法的 O(n\log{n}+m\log{m}+k\log{k}) 实现了最窄瓶颈处的优化，在此题的数据范围中可以显然看出优化之大。

核心代码

Upd:修复了一点小问题(?)

Upd:补上了Fib堆优化Dij的大坑。。。