1.
网络
流
的
一些
基
本
概
念
点击阅读
很多同学建立过网络流模型做题目, 也学过了各种算法, 但是对于基本的概念反而说不清楚. 虽然不同的模型在具体
叫法上可能不相同, 但是不同叫法对应的思想是一致的. 下面的讨论力求规范, 个别地方可能需要对通常的叫法加以澄清.
求解可行流: 给定一个网络流图, 初始时每个节点不一定平衡 (每个节点可以有盈余或不足), 每条边的流量可以有上
下界, 每条边的当前流量可以不满足上下界约束. 可行流求解中没有源和汇的概念, 算法的目的是寻找一个可以使所有节
点都能平衡, 所有边都能满足流量约束的方案, 同时可能附加有最小费用的条件 (最小费用可行流).
求解最大流: 给定一个网络流图, 其中有两个特殊的节点称为源和汇. 除源和汇之外, 给定的每个节点一定平衡. 源可
以产生无限大的流量, 汇可以吸收无限大的流量. 标准的最大流模型, 初始解一定是可行的 (例如, 所有边流量均为零), 因
此边上不能有下界. 算法的目的是寻找一个从源到汇流量最大的方案, 同时不破坏可行约束, 并可能附加有最小费用的条
件 (最小费用最大流).
扩展的最大流: 在有上下界或有节点盈余的网络流图中求解最大流. 实际上包括两部分, 先是消除下界, 消除盈余, 可
能还需要消除不满足最优条件的流量 (最小费用流), 找到一个可行流, 再进一步得到最大流. 因此这里我们的转化似乎是
从最大流转化为可行流再变回最大流, 但其实质是将一个过程 (扩展的最大流) 变为了两个过程 (可行流 + 最大流).
以上概念同时适用于最小费用流.
2.
最
小
费
用
流
的
各
种
转
化
点击阅读
不少同学认为消圈算法比增广路算法使用面广, 可以有负边, 负圈, 每个点都能有盈余亏空等等. 实际上增广路算法也
一样可以有负边, 负圈, 上下界等等, 且一般来说速度快于消圈算法.
以下讨论中 为盈余量, 为费用, 为容量.
1.最小费用(可行)流 最小费用最大流
建立超级源 和超级汇 , 对顶点 , 若 添加边 , 若 添加边
, 之后求从 到 的最小费用最大流, 如果流量等于 , 就存在可行流, 残量网络已在原图上
求出.
2.最小费用最大流 最小费用(可行)流
连边 , 所有点 有 , 然后直接求.
3.最小费用(可行)流中负权边的消除
直接将负权边满流.
4.最小费用最大流中负权边的消除
先连边 , 使用 (3.) 中的方法消除负权边, 使用 (1.) 中的方法求出最小费用 (可行) 流, 之后
距
离
标
号
不
变
, 再求最小费用最大流; 注意此时增广费用不能机械使用源点的标号——应该是源点汇点标号之差.
3.
费
用
流
中
的
负
边
和
负
圈
点击阅读
在费用流的求解中难免会遇到负边和负圈的问题. 对于消圈算法, 负圈就是算法本身的一部分; 但对于增广路算法, 负
圈是我们所不愿意看到的. 鉴于竞赛中使用消圈算法将带来严重的效率问题, 我们必须探索使用增广路算法处理费用流负