algorithm - 改进 Dinic 算法的动态树数据结构

Question

我想将 Dinic 的算法与动态树一起应用。但我找到的来源很少。特别是关于动态树。如果有一个带有详细解释的好的源代码或一些使用动态树的简单源代码，那就太好了。

有没有人遇到过这样的事情？提前致谢

Answer 1

改进的基本思想是避免 Dinic 算法中的过早悲观化。与预流/推算法相反，Dinic 的算法在剩余流图中搜索路径。一旦处理了这样的流程，修改后的算法将处理在先前搜索中找到的路径，而不是开始新的搜索。

你可以在这里找到一个非常易读的介绍，包括数据结构本身的实现。这里有更详细的讲座。最后，A Data Structure for Dynamic Trees（由 Sleator 和 Tarjan 撰写）是专注于数据结构本身实现的原始论文。