最大流算法之ISAP

网络流(最大流)实在是个玄而又玄的东西.就是一个异常简单的模型,可以想象成是一个管道网络,各个管道有各自的单位时间最大通过的流量,问单位时间从其中某一个点(源点)到另一个点(汇点)能通过的最大流量.但是这个东西却能解决很多问题,其中的一些问题甚至看起来还和这个模型没啥关系,但是巧妙地构建关系建立出一张图之后就会发现,这玩意居然能用最大流的思想解.

因此,掌握一种快速求解最大流问题的算法就异常重要了.大名鼎鼎的 Ford-Fulkerson算法 的效率过低, EdmondsKarp算法 虽有改进但是依然不够,直到 Dicnic算法 运用类似启发式搜索的思想将时间复杂度降低到$O(V^2E)$,才刚刚称得上是比较高效.而在此基础上,采用类似思路的 ISAP算法 则使用了动态的层次图,省略了Dicnic算法中BFS的过程,效率进一步提高(虽然理论的时间复杂度没有改变,仍然是$O(V^2E)$).

虽然初次用ISAP水过了洛谷的 最大流模板题 ,但是依然担心自己还是没有掌握,于是在这里总结一下.

前置知识

ISAP的代码很简单,在Dicnic的基础上也比较容易理解.因此再研究ISAP之前要先研究这些:

  • 网络流的基本概念
  • Dicnic算法
  • 链式前向星(邻接链表)

ISAP的基本思想

ISAP的思路的Dicnic是几乎一样的,生成(计算)每个节点的高度,层次(定义为当前节点到汇点的最短距离),搜索中每次前进只会走到高度比当前节点低1的节点,因此能保证总是向着汇点前进的,避免了向着反方向或是同层访问一些多余的节点,是典型的启发式搜索.

那么就会遇到一个问题:如果在某个节点,我们发现无路可走了,怎么办?如果是这个点不可能再向它连接的其他节点发送流量了,那么似乎还没有什么问题;如果无路可走是因为高度的限制,会不会损失一部分解?

这就是ISAP的核心:重贴标签.当我们发现出现了这种情况,我们重新标记当前节点的高度.为了不漏掉某些解,显然我们应该将它的高度设为比它连接的且边上还有富裕容量的节点中高度最小的节点大1.这就是所谓的 重贴标签.

具体实现

本文标题:最大流算法之ISAP

文章作者:Snake

发布时间:2018年03月30日 - 21:03

最后更新:2018年04月28日 - 20:04

原始链接:https://snake.moe/2018/03/30/最大流算法之ISAP/

许可协议: 署名-非商业性使用-相同方式共享 4.0 国际 转载请保留原文链接及作者。