运筹学---最大流问题

简单复习一下最大流问题以及最小费用最大流问题

基本概念

一个赋权有向图称为网络，每个弧对应一个称为弧的容量

网络上的流是定义在弧集合上的一个函数f，称为流量

可行流指的是满足条件 并且对于中间点，流入量=流出量

对于发点的流出量等于收点的流入量，称为这个可行流的流量，记为

最大流问题是要求的最大值，并找到此时的流f

增广链

增广链是从发点到收点的一条链，满足这个链中正方向的弧（称为非饱和弧），反方向的弧（称为非零流弧）

（正向指的是这条弧的方向和链从起点到终点的方向相同，反向反之）

可看到，如果找到一个增广链，就可以调整这个增广链上面的流，让前向弧上的f增加，后向弧上面的f减少，调整的数字相同保证调整后的流仍然是可行流，并且流量增加。

寻取最大流的标号法

从一个可行流出发，不断调整使得这个流的流量增加，直到不能进行。

可行流必定存在，因为零流就是可行流。

调整过程

以下的标号和调整进行一次，就可以找到一条增广链并且将这条增广链上的流量尽量调整到最大

标号和调整不是一劳永逸的，因此每找一条增广链就要重新标号。

标号

思路说明

这是一个图及其上面的可行流，弧上标的是，即这条弧的容量和流量

标号指的是给每个顶点标号，标的什么号？通俗的说是记录从某个前面的点到这个顶点的流入量可以增加的余地（记为)

（当然上面说的“流入量”是我瞎编的，字面意思，解释不清，l的具体定义见具体步骤）

一条链中一个顶点的流入量受限于两个因素(important)

• 这个顶点之前的弧的容量
• 这个顶点的前一个顶点的

因为每次调整的目的是找到一条增广链，因此上面说的“增加”指的是这个点相邻的某一条弧上流量增加而导致这条弧流入量的增加，仅仅局限于一条增广链。为了找到这条增广链，同时也要记录影响这个弧的前一条弧。

因此，标号要记录的是我们上面说的l，以及导致l的顶点，为了和书上统一：

具体步骤

1. 标记发点为，这个0没什么意思
2. 从已标号的点开始，对所有相邻的没标号的点
   • 如果是弧，并且这条弧不饱和，就给标号，
   • 如果是弧，并且是非零流弧，就给标号，
3. 经过了2 的称为已检查的，如果所有标号顶点都是已检查的，并且标号进行不下去的时候，就得到最大流，具体解释见后

调整

经过上面的标号步骤，收点也被标上号，顺着收点的标号向前追踪，就能找到一条增广链

在这条增广链上前向弧的流量增加，后向弧的流量减少，这样，总流量就增加了

调整结束后继续转入标号程序

判断已达到最大流

截集及其相关定义

将网络的点集V分为两个集合 ，使得，则弧集称为分离的截集

截集的流量（截量）

可以证明 最大流的流量等于截量的最小值

判断条件

如图，当标完之后，检查这两个顶点发现标号无法进行，因为与相邻的每条弧都是饱和弧或者零流弧，集合{}构成截集，并且可以证明当前这个流的流量等于截集的截量

所以当前流就是最大流

---

最小费用最大流

最大流可能有多个，要找到费用最小的最大流

基本定义

单位流量费用

总费用计算公式

思路

首先，零流是对应流量的最小费用流（因为费用都是正的

增广链的费用

增广链的费用指的是这条链的流量增加1，这条链上的费用的增加量，等于

递推

如果是流量为的流里面费用最小的，是最小费用的增广链，那么沿调整得到的f必然是流量为的流里面费用最小的

每次都沿着最小费用增广链调整，最终得到的f就是最小费用流

问题转化为如何寻找最小费用增广链

这本质上又是一个最短路问题

要求找到的最短路里面的弧都是非饱和弧或者零流弧

可以构造一个新的图，顶点和原图一样，把原来的每一条弧变成两条方向相反的弧，权为

（或者直接删掉正无穷的这些弧

找到这个图从发点到收点的最短路就得到了最小费用增广链