从入门到精通：最小费用流的“zkw算法”.docVIP

从入门到精通最小费用流的“zkw算法” 网络流的一些基本概念 很多同学建立过网络流模型做题目, 也学过了各种算法, 但是对于基本的概念反而说不清楚. 虽然不同的模型在具体叫法上可能不相同, 但是不同叫法对应的思想是一致的. 下面的讨论力求规范, 个别地方可能需要对通常的叫法加以澄清. 求解可行流: 给定一个网络流图, 初始时每个节点不一定平衡 (每个节点可以有盈余或不足), 每条边的流量可以有上下界, 每条边的当前流量可以不满足上下界约束. 可行流求解中没有源和汇的概念, 算法的目的是寻找一个可以使所有节点都能平衡, 所有边都能满足流量约束的方案, 同时可能附加有最小费用的条件 (最小费用可行流). 求解最大流: 给定一个网络流图, 其中有两个特殊的节点称为源和汇. 除源和汇之外, 给定的每个节点一定平衡. 源可以产生无限大的流量, 汇可以吸收无限大的流量. 标准的最大流模型, 初始解一定是可行的 (例如, 所有边流量均为零), 因此边上不能有下界. 算法的目的是寻找一个从源到汇流量最大的方案, 同时不破坏可行约束, 并可能附加有最小费用的条件 (最小费用最大流). 扩展的最大流: 在有上下界或有节点盈余的网络流图中求解最大流. 实际上包括两部分, 先是消除下界, 消除盈余, 可能还需要消除不满足最优条件的流量 (最小费用流), 找到一个可行流, 再进一步得到最大流. 因此这里我们的转化似乎是从最大流转化为可行流再变回最大流, 但其实质是将一个过程 (扩展的最大流) 变为了两个过程 (可行流 + 最大流). 以上概念同时适用于最小费用流. 最小费用流的各种转化 不少同学认为消圈算法比增广路算法使用面广, 可以有负边, 负圈, 每个点都能有盈余亏空等等. 实际上增广路算法也一样可以有负边, 负圈, 上下界等等, 且一般来说速度快于消圈算法.以下讨论中 为盈余量, 为费用, 为容量. 最小费用(可行)流 最小费用最大流建立超级源 和超级汇 , 对顶点 , 若 添加边 , 若 添加边 , 之后求从 到 的最小费用最大流, 如果流量等于 , 就存在可行流, 残量网络已在原图上求出. 最小费用最大流 最小费用(可行)流连边 , 所有点 有 , 然后直接求. 最小费用(可行)流中负权边的消除直接将负权边满流. 最小费用最大流中负权边的消除 先连边 , 使用 (3.) 中的方法消除负权边, 使用 (1.) 中的方法求出最小费用 (可行) 流, 之后距离标号不变, 再求最小费用最大流; 注意此时增广费用不能机械使用源点的标号——应该是源点汇点标号之差. 费用流中的负边和负圈 在费用流的求解中难免会遇到负边和负圈的问题. 对于消圈算法, 负圈就是算法本身的一部分; 但对于增广路算法, 负圈是我们所不愿意看到的. 鉴于竞赛中使用消圈算法将带来严重的效率问题, 我们必须探索使用增广路算法处理费用流负边和负圈的方法.对于单纯的负边, 如果这些负边没有组成负圈, 可以使用重赋权技术来处理, 即通过对每个节点合适的顶标, 使得 Reduced Cost 非负. 这个顶标通常可以使用到汇点的距离, 修改之后的边权变为 . 根据流量平衡条件, 容易根据这个新的费用算出原费用, 同时可以证明这样的重赋权不改变最优解. 这样做的代价是一次 SPFA 操作, 时间耗费是相对较小的.如果存在负圈, SPFA 算法将不会终止. 很多同学使用人为的限制条件使其终止, 这是错误的. 举一个例子: 源点和汇点均为孤立点, 图中另外存在一个负费用, 正容量的圈. 不管怎样初始标号, 仅凭增广无法消除这个负圈, 从而得不到最优解 (根据最小费用最大流的定义, 要在所有最大流 (流量都为 ) 中寻找一个费用最小的方案). 也许你会说这个例子太过极端, 但是也很容易构造出其他一些例子, 说明不处理负圈, 或者简单地对算法打补丁并不能解决本质问题.解决方法就是将所有负费用的边强制满流, 称为“退流”操作. 这样做之后我们破坏了平衡条件, 但满足了最优条件. 之后我们可以先求可行流, 再求最大流, 其间一直维持最优条件, 并逐步解决平衡条件, 最大流条件等问题. 这也就是 (2.) 中提到的方法. 这个方法可以消除所有负权边 (在 Reduced Cost 意义下), 同时正确处理所有负圈问题. 那么, 这个方法的速度如何呢?费用流相关的图大致可以分为两类, 一类图侧重于费用, 即总的流量不大, 如 Two Shortest (只有 ), KaKas Matrix Travels 等. 较为通用的强制满流方法在这类图上表现不佳, 原因是原本的流量较小而负费用较多, 经过转化的图在可行流求解阶段流量与原流量相比很大, 严重影响速度. 另一方面, 这