用于改进 Dinic 算法的动态树数据结构

Question

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

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

Answer 1

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

您可以在这里找到一个非常可读的介绍，包括数据结构本身的实现。这是更详细的讲座。最后，动态树的数据结构（由 Sleator 和 Tarjan 撰写）是原始论文，重点关注数据结构本身的实现。