《从入门到精通最小费用流的“zkw算法”》由会员分享，可在线阅读，更多相关《从入门到精通最小费用流的“zkw算法”（9页珍藏版）》请在金锄头文库上搜索。
1、从入门到精通最小费用流的 zkw算法 1 网络流的一些基本概念 很多同学建立过网络流模型做题目 也学过了各种算法 但是对于基本的概念反而说不清楚 虽然不同的模型在具 体叫法上可能不相同 但是不同叫法对应的思想是一致的 下面的讨论力求规范 个别地方可能需要对通常的叫法加 以澄清 求解可行流 给定一个网络流图 初始时每个节点不一定平衡 每个节点可以有盈余或不足 每条边的流量可以 有上下界 每条边的当前流量可以不满足上下界约束 可行流求解中没有源和汇的概念 算法的目的是寻找一个可 以使所有节点都能平衡 所有边都能满足流量约束的方案 同时可能附加有最小费用的条件 最小费用可行流 求解最大流 给定一个网
2、络流图 其中有两个特殊的节点称为源和汇 除源和汇之外 给定的每个节点一定平衡 源可以产生无限大的流量 汇可以吸收无限大的流量 标准的最大流模型 初始解一定是可行的 例如 所有边流 量均为零 因此边上不能有下界 算法的目的是寻找一个从源到汇流量最大的方案 同时不破坏可行约束 并可 能附加有最小费用的条件 最小费用最大流 扩展的最大流 在有上下界或有节点盈余的网络流图中求解最大流 实际上包括两部分 先是消除下界 消除盈 余 可能还需要消除不满足最优条件的流量 最小费用流 找到一个可行流 再进一步得到最大流 因此这里我 们的转化似乎是从最大流转化为可行流再变回最大流 但其实质是将一个过程 扩展的最大
3、流 变为了两个过程 可行流 最大流 以上概念同时适用于最小费用流 2 最小费用流的各种转化 不少同学认为消圈算法比增广路算法使用面广 可以有负边 负圈 每个点都能有盈余亏空等等 实际上增广路算 法也一样可以有负边 负圈 上下界等等 且一般来说速度快于消圈算法 以下讨论中为盈余量 为费用 为容量 1 最小费用 可行 流最小费用最大流 建立超级源和超级汇 对顶点 若 添加边 若添加边 之后求从到 的最小费用最大流 如果流量等于 就存在可行流 残量网络已在 原图上求出 2 最小费用最大流最小费用 可行 流 连边 所有点 有 然后直接求 3 最小费用 可行 流中负权边的消除 直接将负权边满流 4 最小
4、费用最大流中负权边的消除 先连边 使用 3 中的方法消除负权边 使用 1 中的方法求出最小费用 可 行 流 之后距离标号不变 再求最小费用最大流 注意此时增广费用不能机械使用源点的标号 应该是源点汇 点标号之差 3 费用流中的负边和负圈 3 费用流中的负边和负圈 在费用流的求解中难免会遇到负边和负圈的问题 对于消圈算法 负圈就是算法本身的一部分 但对于增广路算 法 负圈是我们所不愿意看到的 鉴于竞赛中使用消圈算法将带来严重的效率问题 我们必须探索使用增广路算法 处理费用流负边和负圈的方法 对于单纯的负边 如果这些负边没有组成负圈 可以使用重赋权技术来处理 即通过对每个节点合适的顶标 使得 Re
5、duced Cost 非负 这个顶标通常可以使用到汇点的距离 修改之后的边权变为 根据流量 平衡条件 容易根据这个新的费用算出原费用 同时可以证明这样的重赋权不改变最优解 这样做的代价是一次 SPFA 操作 时间耗费是相对较小的 如果存在负圈 SPFA 算法将不会终止 很多同学使用人为的限制条件使其终止 这是错误的 举一个例子 源点和 汇点均为孤立点 图中另外存在一个负费用 正容量的圈 不管怎样初始标号 仅凭增广无法消除这个负圈 从而 得不到最优解 根据最小费用最大流的定义 要在所有最大流 流量都为0 中寻找一个费用最小的方案 也许你 会说这个例子太过极端 但是也很容易构造出其他一些例子 说明
6、不处理负圈 或者简单地对算法打补丁并不能解 决本质问题 解决方法就是将所有负费用的边强制满流 称为 退流 操作 这样做之后我们破坏了平衡条件 但满足了最优条 件 之后我们可以先求可行流 再求最大流 其间一直维持最优条件 并逐步解决平衡条件 最大流条件等问题 这也就是 2 中提到的方法 这个方法可以消除所有负权边 在 Reduced Cost 意义下 同时正确处理所有负圈 问题 那么 这个方法的速度如何呢 费用流相关的图大致可以分为两类 一类图侧重于费用 即总的流量不大 如 Two Shortest 只有2 KaKa s Matrix Travels 等 较为通用的强制满流方法在这类图上表现不佳
7、 原因是原本的流量较小而负费用较多 经过转 化的图在可行流求解阶段流量与原流量相比很大 严重影响速度 另一方面 这类图往往有深刻的最短路背景 从 而不会出现负圈 可以使用 SPFA 重赋权 另一类图侧重于流量 即边的费用相差不大 如 employee 最优图像 的求解 这种图中流量不小而负费用相对有限 也可以稍大 关键是前者 经过转化增加的流量可以很快完成计 算 因此强制满流方法就没有问题 另外 不同的建图方式有可能造成不同的模型 在 employee 这道题中 如果建图时从每个点向后连边 从前向后 运行最小费用最大流 这时的算法就只有负边 没有负圈 而如果从每个点向前连边 在整个图上求最小费
8、用平衡 流 就会有负圈出现 但是这里并没有本质区别 将第二种模型中的所有向前连的边强制满流即可得到第一种模 型 如果将其他的负边也强制满流还能得到一个完全没有负边的模型 大家可能也猜到了 这几种模型在速度上相 去不远 毕竟根据我们刚才的讨论 增加的流量在算法的执行中不占主要地位 4 最小费用流的 zkw算法 最小费用流在 OI 竞赛中应当算是比较偏门的内容 但是 NOI2008 中 employee 的突然出现确实让许多人包括 zkw 自己措手不及 可怜的zkw当时想出了最小费用流模型 可是他从来没有实现过 所以不敢写 此题 0 分 zkw 现 在对费用流的心得是 虽然理论上难 但是写一个能
9、AC 题的费用流还算简单 先贴一个我写的costfl ow 程序 只 有不到 70 行 费用流比最大流还好写 Code include include using namespace std const int maxint 0U 1 int n m pi1 cost 0 bool v 550 struct etype int t c u etype next pair etype etype int t int c int u etype next t t c c u u next next void operator new unsigned void p return p e 550 i
10、nt aug int no int m if no n return cost pi1 m m v no true int l m for etype i e no i i i next if i u i u d i pair u d l d if l return m return m l bool modlabel int d maxint for int i 1 inext if j u if d maxint return false for int i 1 inext j c d j pair c d pi1 d return true int main freopen costfl
11、ow in r stdin freopen costflow out w stdout scanf d d etype Pe new etype m m while m 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 这里使用的是连续最短路算法 最短路算法 为什么程序里没有 SPFA Dijkstra 且慢 先让我们回顾一下图论中 最短路算法中的
12、距离标号 定义为点 的距离标号 任何一个最短路算法保证 算法结束时对任意指向顶点 从 顶点 出发的边满足 条件1 且对于每个 存在一个 使得等号成立 条件2 换句话说 任何一 个满足以上两个条件的算法都可以叫做最短路 而不仅仅是 SPFA Dijkstra 算法结束后 恰在最短路上的边满足 在最小费用流的计算中 我们每次沿的路径增广后都不会破坏条件 1 但是可能破坏了条件 2 不 满足条件 2 的后果是什么呢 使我们找不到每条边都满足新的增广路 只好每次增广后使用 Dijkstra SPFA 等等算法重新计算新的满足条件 2 的距离标号 这无疑是一种浪费 KM 算法中我们可以修改不断 修改可行
13、顶标 不断扩大可行子图 这里也同样 我们可以在始终满足条件 1 的距离标号上不断修改 直到可以继 续增广 满足条件 2 回顾一下 KM 算法修改顶标的方法 根据最后一次寻找交错路不成功的 DFS 找到 左边的点增加 右边的点减少 这里也一样 根据最后一次寻找增广路不成功的 DFS 找到 所有访问过的点距离标号增加 可以证明 这样不会破坏性质 1 而且至少有 一条新的边进入了的子图 算法的步骤就是初始标号设为0 不断增广 如果不能增广 修改标号继续增广 直到彻底不能增广 源点的标号已 经被加到了 注意 在程序中所有的 cost 均表示的是 reduced cost 即 另外 这个算 法不能直接用
14、于有任何负权边的图 更不能用于负权圈的情况 有关这两种情况的处理 参见 2 和 3 中的 说明 这样我们得到了一个简单的算法 只需要增广 改标号 各自只有 7 行 不需要 BFS 队列 SPFA 编程复杂度很 低 由于实际的增广都是沿最短路进行的 所以理论时间复杂度与使用 SPFA 等等方法的连续最短路算法一致 但 节省了SPFA或者Dijkstra的运算时间 实测发现这种算法常数很小 速度较快 employee这道题所有数据加在一起 耗时都在2s之内 5 zkw 费用流算法在哪些图上慢 实践中 上面的这个算法非常奇怪 在某一些图上 算法速度非常快 另一些图上却比纯 SPFA 增广的算法慢 不
15、 少同学经过实测总结的结果是稠密图上比较快 稀疏图上比较慢 但也不尽然 这里我从理论上分析一下 究竟这 个算法用于哪些图可以得到理想的效果 int s t c u scanf d d d d e s new Pe etype t c u e s e t new Pe etype s c 0 e t e s pair e t e t pair e s do do memset v 0 sizeof v while aug 1 maxint while modlabel printf d n cost return 0 54 55 56 57 58 59 60 61 62 63 64 65 66
16、67 先分析算法的增广流程 和 SPFA 直接算法相比 由于同属于沿最短路增广的算法 实际进行的增流操作并没有太 多的区别 每次的增流路径也大同小异 因此不考虑多路增广时 增广次数应该基本相同 运行时间上主要的差异 应当在于如何寻找增流路径的部分 那么 zkw 算法的优势在于哪里呢 与 SPFA 相比 KM 的重标号方式明显在速度上占优 每次只是一个对边的扫描 操作而已 而SPFA需要维护较为复杂的标号和队列操作 同时为了修正标号 需要不止一次地访问某些节点 速度 会慢不少 另外 在 zkw 算法中 增广是多路进行的 同时可能在一次重标号后进行多次增广 这个特点可以在许 多路径都费用相同的时候派上用场 进一步减少了重标号的时间耗费 下面想一想 zkw 算法的劣势 也就是 KM 重标号方式存在的问题 KM 重标号的主要问题就是 不保证经过一次重 标号之后能够存在增广路 最差情况下 一次只能在零权网络中增加一条边而已 这时算法就会反复重标号 反复 尝试增广而次次不能增广 陷入弄巧成拙的境地 接下来要说什么 大家可能已经猜到了 对于最终流量较大 而费用取值范围不大的图 或者是增广路径比较短的
