Question

所谓伊人，在水一方。溯洄从之，道阻且长；溯游从之，宛在水中央。《诗经．蒹葭》

Flow Network

把一张图想成是水流管线图。图上的边想成是水管：边的权重想成是水管的容量上限（容量下限预设为零），有向边仅允许单向流动，无向边得同时双向流动。图上的点想成是水管的接合点，并附有控制水流流向与流量的机器：点的权重想成是接合处的容量上限（容量下限预设为零），但是大家一般都不考虑点的权重。

每一条管线的流量数值与容量上限数值，以一斜线区隔，标记于图上各条边，方便观看。水流流动时必须遵守各条管线的容量限制，不得有逾越容量限制之情事。流量数值与容量上限数值一定是正值或零，不得为负值。

在这张水流管线图当中，水流流速是稳定的、是源源不绝的，有变化的只有水流流向与流量。因此，水流流动时，只要关心各条管线的方向限制和容量限制就可以了。

当一张图专门用于水流流动时，则可称之为 Flow Network，中译为“流网路”。

“流网路”只有容量资讯，没有流量资讯。

s-t Flow

在图上选定一个源点（source，标记为 s）和一个汇点（sink，标记为 t），源点灌水，汇点泄水，并控制水流从源点流至汇点，中途不得渗漏、不得淤滞。

s-t Flow 以下简称为“流”。一个流便是由源点经管线至汇点的水流。一个流的流量，即是源点灌入的水流流量，同时也是汇点泄出的水流流量。

“流”只有流量资讯，没有容量资讯。

Maximum s-t Flow

“最大流”。给定一张图，以及给定一个源点与一个汇点，所有可能的 Flow 当中，流量最大者便是 Maximum Flow，可能会有许多个。

在源点一口气灌入大量的水，藉由调整各条管线的流量与流向，让汇点泄出的流量最多。

Minimum s-t Flow

“最小流”。一滴水都不流，管线裡都没水，就是 Min-Flow，流量为零。大家应该都懂，所以就讨论到这裡了。

图例：不属于流的玩意

水流流到无法流动的地方，水流淤滞而无法流至汇点，不能称作流。

图例：合流、分流、交流

水流可以在任何点上合流、分流、交流──简单地来说，就是每个点之中，流入与流出的水量要相等，至于要怎麽分合都无所谓。

图例：产生迴圈的流

产生迴圈的流会佔据管线容量，令流量难以再增加，是一种浪费。

图例：源点与汇点在一起的流

感情很好的两个点，一般视作内地裡波涛汹涌，表面上流量为零。

多个源点和多个汇点变成一个源点和一个汇点

先前都只讨论一个源点和一个汇点的原因，其实是因为多个源点可以转化成一个源点、多个汇点可以转化成一个汇点。当图上有多个源点时，就在图上新增一个超级源点，连向这些源点，边的容量都设定为无限大。如此一来，就可以只留下一个超级源点，并取消原本的源点了。汇点的道理亦同。

因此，在 s-t Flow 当中，多个源点和多个汇点可以改为一个源点和一个汇点，最后只讨论一个源点和一个汇点就可以了。事情也变简单多了。

点的容量变成边的容量

先前提到大家一般不考虑点的容量，其实是因为点的容量可以转化为边的容量。把 P 点改成两个点 Pin 和 Pout，原先连到 P 点的边变成连到 Pin，由 P 点连出的边变成由 Pout 连出，P 点的容量则由一条 Pin 到 Pout 的边来取代之。

因此，在 s-t Flow 当中，点的容量可以改为边的容量，最后只需要考虑边的容量就行了。只考虑边的容量，事情也变简单多了。

多重的边变成单独的边

无向图中，当两点之间有多重的边，就可以加总这些边的容量限制，合併成单独的边；有向图中，当一点到另一点有多重的边，就可以加总这些边的容量限制，合併成单独的边。

因此，在 s-t Flow 当中，多重的边可以改为单独的边，最后只讨论“无向图：两点间仅有一条边、有向图：一点到另一点仅有一条边”就可以了。事情也变简单多了。

来回水流变成单向水流

两点之间，两条方向相反的有向边，等量减少来向与回向的水流，不会影响总流量，也不会违背规则。

因此，在 s-t Flow 当中，来回水流可以变成单向水流，最后只要从中选择一条边来流动就可以了。事情也变简单多了。

无向边变成有向边

无向边得同时双向流动。一条无向边可以改为两条方向相反的有向边，可是必须共用容量。

由于来回水流可以变成单向水流，所以上述两条方向相反的有向边，其实不必共用容量，宛如普通的有向边。

因此，在 s-t Flow 当中，一条无向边可以变成两条方向相反的有向边，最后只讨论有向边就可以了。事情也变简单多了。

Max-Flow Min-Cut Theorem

一条涓流的流量与瓶颈

水从源点流至汇点，中途不会渗漏、不会淤滞。一条由源点流至汇点的小小涓流，其流动路径当中，每一条边的流量，都会是小小涓流的流量。

水流流动时要符合管线容量限制。一条由源点流至汇点的小小涓流，其流量的瓶颈，会是流动路径当中，容量上限最低的一条边。

一个流的总流量与瓶颈（一）

水从源点流至汇点，中途不会渗漏、不会淤滞。现在把图上的点，依地理位置划分作两区，一区邻近源点，另一区邻近汇点──一个从源点流至汇点的流，“由源点流至汇点的总流量”会等于“由源点区流入到汇点区的总流量”减去“由汇点区流回到源点区的总流量”。无论是哪一种分区方式，都有这种性质。

水流流动时要符合管线容量限制。一个从源点流至汇点的流，“由源点区流入到汇点区的总流量”会小于等于“由源点区横跨到汇点区的管线总容量”。反方向亦同。

也就是说，一个从源点流至汇点的流，其总流量的瓶颈，会出现在“由源点区横跨到汇点区的管线总容量”最低的一种分区方式。

一个流的总流量与瓶颈（二）

【读者若不懂 s-t Cut，请参考本站文件“ Cut ”。】

方才的分两区方式有点笼统，很难定义谁邻近源点，谁邻近汇点，因此资讯学家尝试以 s-t Cut 来取代方才的说法，希望藉由 s-t Cut 把事情说得更严谨一些。然而事情也稍微变得複杂了。

水从源点流至汇点，中途不会渗漏、不会淤滞。现在把图上的点，利用 s-t Cut 的概念划分作两侧，一侧包含源点，另一侧包含汇点──一个从源点流至汇点的流，“由源点流至汇点的总流量”会等于“由源点侧流入到汇点侧的总流量”减去“由汇点侧流回到源点侧的总流量”。无论是哪一种划分方式，都有这种性质。

水流流动时要符合管线容量限制。一个从源点流至汇点的流，“由源点侧流入到汇点侧的总流量”会小于等于“由源点侧横跨到汇点侧的管线总容量”。反方向亦同。

也就是说，一个从源点流至汇点的流，其总流量的瓶颈，会出现在“由源点侧横跨到汇点侧的管线总容量”最低的一种分区方式。也就是容量的 Minimum s-t Cut。

Max-Flow Min-Cut Theorem

“最大流最小割定理”其实就是谈瓶颈。“网路流量的最大 s-t 流”等于“管线容量的最小 s-t 割”，管线若还有空间，就儘量增加流量，直到遇到瓶颈，瓶颈会出现在容量的最小 s-t 割。

打个比方来说，在一个装水的塑胶袋底部戳洞，水就会流出来；戳越多洞，水就流出的越多。这表示水一旦有隙可乘，就一定会源源而来、滔滔而至，乃增加流量。水一旦无隙可乘，流量达到上限，此刻就是最大流了。

要找最大流，可以运用“最大流最小割定理”的概念，让水流不停地鑽空隙流至汇点，当无法再找到空隙时，就是极限了，就是最大流了。

若只找最大流流量，则可以运用求最小 s-t 割的演算法，计算管线容量的最小 s-t 割的权重，此即等同于最大流流量。

Maximum s-t Flow: Augmenting Path Algorithm（Ford-Fulkerson Algorithm）

用途

给定一张图，并给定源点、汇点，找出其中一个最大流。

Flow Decomposition

一个流是由许多条小小涓流逐渐聚集而成的。我们可以用一条一条的小小涓流，累积出最大流。

溯洄冲减
【注：此概念目前尚未有专有名词】

然而有些涓流的路径不理想，浪费了管线空间。有鉴于此，演算法作者设计了一个手法：溯洄冲减。流出第一条涓流之后，第二条涓流可以溯洄上一条流的部份路段，然后到达汇点。正流与逆流相互冲减的结果，使得相互交织的两条涓流，成为两条独立的涓流。如此一来，就算涓流的路径不理想，之后仍可靠溯洄冲减来调整路径。

【注：涓流、溯洄、冲减这三个词，是初次使用。我参考字典后，觉得意义相近，而选用的。而且它们都是水字旁！】

溯洄冲减的时候，可以选择水量多寡和路线位置，藉以调整成不同的流。

溯洄冲减的概念可以用于许多地方。这裡列出一些相关问题，供各位练习。

UVa 10806 10380

Residual Network

每次增加一条小小涓流，都要时时刻刻遵守各条管线的容量限制。管线要有剩馀空间，或者管线有溯洄冲减的机会，涓流才能流过管线。

一个便捷的整合方式是：管线的剩馀空间再加上可供溯洄冲减的水量，称作“剩馀容量（Residual Capacity）”；所有管线的剩馀容量，整体可视作一张图，称作“剩馀网路（Residual Network）”。

如此一来，涓流要进行流动，其实只要参考剩馀网路，遵守各条管线的剩馀容量限制就可以了。

剩馀网路是一个高度抽象概念，为的是整合涓流流动的容量限制。实作程式码时，可以直接建立一个剩馀网路的资料结构，随时利用容量与剩馀容量来计算流量。

Augmenting Path

“扩充路径”，剩馀网路上面一条由源点到汇点的路径。换个角度想，把握管线的剩馀空间，把握溯洄冲减，找出一条由源点至汇点的小小涓流路径，就是一条扩充路径。

扩充路径是一条可以扩充总流量的路径，扩充的流量可多可少，一般来说流量越多越好，到达瓶颈最好，能较快达到最大流。

扩充路径的长度范围是 1 到 V-1（长度为 0 表示源点与汇点重叠）。当一条扩充路径超过 V-1 条边，则会形成浪费管线容量的迴圈，此时应消除迴圈之后，再来作为扩充路径。

演算法

不断找扩充路径，并扩充流量。直到没有扩充路径为止。

所有扩充路径总合起来，就是最大流。
所有扩充路径的流量总和，就是最大流流量。

扩充路径要怎麽找都可以，
不一样的扩充路径有机会产生不一样的最大流。

还找得到扩充路径：
表示目前不是最大流，因为藉由扩充路径，还可以再增加总流量。

找不到扩充路径：
表示源点往汇点方向的一些关键管线已经没有剩馀容量。没有剩馀容量可推导出：
甲、管线没有剩下来的空间（或根本没有管线），也就是遭遇瓶颈。
乙、不能溯洄冲减。
根据最大流最小割定理，遭遇瓶颈时即是最大流。
【注：这部分的证明有漏洞。没有考虑到形成迴圈的涓流。】

这个演算法的绝妙之处，是导入了溯洄冲减的机制，藉以调整流动路径；然后把溯洄冲减併入了容量限制的思维，创立剩馀网路、扩充路径等抽象概念；最后返回到最大流最小割定理，间接证明了溯洄冲减无论在什麽情况下，都能调整好流动路径，找出最大流──调校水流的本质，就是剩馀网路。

另外可以发现，在整个过程当中，所有管线的剩馀容量的总和是固定不变的──只是源点往汇点方向的剩馀容量越来越少，汇点往源点方向的剩馀容量越来越多。整个过程可以看作是在调整剩馀网路的势力走向──每次以扩充路径扩充流量后，正方向会减少对应的剩馀容量，逆方向会增加对应的剩馀容量，源点与汇点之间的势力差距越来越大。

时间複杂度

找一条扩充路径为一次 Graph Traversal 的时间。图的资料结构使用 adjacency matrix 为 O(V^2)；图的资料结构使用 adjacency lists 为 O(V+E)，这裡省略 V 写成 O(E)。

最差情况是，不断找到流量超级少的扩充路径，共找到 F 条，F 是最大流的流量。因此总时间複杂度，依据资料结构的不同，分别为 O(V^2 * F) 与 O(EF)。

如何记录容量、流量、剩馀容量

为了实现溯洄冲减的概念，要是两点之间只有单独一条有向边，就添配一条反向边，让双向都有边；要是两点之间已经是两条方向相反的有向边，就不必更动；要是两点之间是一条无向边，则改成两条方向相反的有向边。

每一条边的容量是定值；至于流量与剩馀容量，则有三种不同的记录方式。第一种记录方式。先前提到，两条方向相反的有向边，可以只让一条边拥有水流，另一条边则没有水流。在此利用没有水流的那条边：两点之间其中一个方向是正流量，是真正流动的方向；另一个方向则是虚设的负流量，用来增加剩馀容量以利溯洄冲减。

一开始还没有水流的时候：
flow(i, j) = 0;
flow(j, i) = 0;

有一条涓流经过边 ij 之后：
flow(i, j) += 流量;
flow(j, i) -= 流量;

有一条涓流经过边 ij，又有一条涓流溯洄冲减，经过边 ji 之后：
flow(i, j) = flow(i, j) + 流量 1 - 流量 2;
flow(j, i) = flow(j, i) - 流量 1 + 流量 2;

最后可归纳得出，当一条涓流经过边 ij 的时候：
flow(i, j) += 流量;
flow(j, i) = -flow(i, j);

真正的流量则是正流量：
true_flow(i, j) = max(flow(i, j), 0);
true_flow(j, i) = max(flow(j, i), 0);

剩馀容量以管线的容量上限和流量相减而得：
residue(i, j) = capacity(i, j) – flow(i, j);
residue(j, i) = capacity(j, i) – flow(j, i);

第二种记录方式。只要有涓流经过了管线，就把涓流流量直接累加在管线流量。虽然这种记录方式会让流量违背容量限制，可是在剩馀容量正确的情况下，还是能找出最大流。

令边 ij 是一条由 i 点到 j 点的边。令边 ji 是一条由 j 点到 i 的边。

一开始还没有水流的时候：
flow(i, j) = 0;
flow(j, i) = 0;

有一条涓流经过边 ij 之后：
flow(i, j) += 流量;
flow(j, i) 保持不变;

有一条涓流经过边 ij，又有一条涓流溯洄冲减，经过边 ji 之后：
flow(i, j) += 流量 1;
flow(j, i) += 流量 2;

最后可归纳得出，当一条涓流经过边 ij 的时候：
flow(i, j) += 流量;
flow(j, i) 保持不变;

真正的流量是把双向流量等量减少后而得（去掉溯洄冲减的部分）：
true_flow(i, j) = flow(i, j) - min(flow(i, j), flow(j, i));
true_flow(j, i) = flow(j, i) - min(flow(i, j), flow(j, i));

剩馀容量以管线的容量上限和双向流量计算而得：
residue(i, j) = capacity(i, j) – (flow(i, j) - flow(j, i));
residue(j, i) = capacity(j, i) – (flow(j, i) - flow(i, j));

第三种记录方式。是第一种记录方式的相反面向，主角改为剩馀容量，只要有涓流经过了管线，正方向剩馀容量会减少，反方向剩馀容量会增加。

令边 ij 是一条由 i 点到 j 点的边。令边 ji 是一条由 j 点到 i 的边。

一开始还没有水流的时候：
residue(i, j) = capacity(i, j);
residue(j, i) = capacity(j, i);

有一条涓流经过边 ij 之后：
residue(i, j) -= 流量;
residue(j, i) += 流量;

有一条涓流经过边 ij，又有一条涓流溯洄冲减，经过边 ji 之后：
residue(i, j) = residue(i, j) - 流量 1 + 流量 2;
residue(j, i) = residue(j, i) + 流量 1 - 流量 2;

最后可归纳得出，当一条涓流经过边 ij 的时候：
residue(i, j) -= 流量;
residue(j, i) += 流量;

真正的流量以管线的容量上限和剩馀流量相减而得，而且是正流量：
true_flow(i, j) = max(capacity(i, j) – residue(i, j), 0);
true_flow(j, i) = max(capacity(j, i) – residue(j, i), 0);

第一种方式最直觉。第二种方式中庸。第三种方式最精简，实作简单，不过最后要计算最大流的时候会比较麻烦。

找出一个最大流＋计算最大流的流量

延伸阅读：容量上限不是有理数的时候

扩充路径永远找不完。

【待补图片】

Maximum s-t Flow: Shortest Augmenting Path Algorithm（Edmonds-Karp Algorithm）

演算法

Augmenting Path Algorithm 的改良版。每次找扩充路径的时候，以源点到汇点的最短路径（想像管线长度皆为 1）作为扩充路径，并且让扩充的流量到达瓶颈。这种方式可以避免浪费管线空间，避免反覆地溯洄冲减，而较快找到最大流。

不断找最短扩充路径，直到找不到为止，即得最大流。
最多找 VE 次就可达到最大流。

达到最大流，估计需要的最短扩充路径数量。
（利用 Edge Labeling with Shortest Distance）

首先将剩馀网路上的每一条边，都标记一个距离数值，数值大小是源点到达该边的最短距离。相同两点之间的正向边与反向边共用一个距离数值。

每次以最短路径扩充流量之后，剩馀网路上一定有某些边的距离数值会增加，并且没有任何一条边的距离数值会减少。也就是说，整体来看，距离数值与日俱增。

在剩馀网路上，以源点到汇点之最短路径，扩充流量至瓶颈之后：

回、最短扩充路径上的正向边：
　口、瓶颈之前的边：
　　距离数值不变。
　口、瓶颈上的边：
　　距离数值会增加。（只剩下反向边能通行，入口在遥远的那端，所以距离数值至少增加一。）
　口、瓶颈之后的边：
　　距离数值会增加。（受到瓶颈断路影响，需绕远路。）
　　也可能不变。（同时有多条最短路径到达该边，只不过其中一条最短路径断了。）

回、最短扩充路径上的反向边：
　　不影响距离数值。

回、最短扩充路径以外的边：
　　距离数值会增加，也可能不变，但是不会减少。

甲、最差的情况下，每次扩充流量后，只有一条边的距离数值有增加 1。乙、图上总共 E 条边，每条边的距离数值范围为 0 到 V-1。以甲乙粗估后，不出 VE 条最短扩充路径，就能达到最大流。

达到最大流，估计需要的最短扩充路径数量。
（利用 Vertex Labeling with Shortest Distance 估计不出结果）

首先将剩馀网路上的每一个点，都标记一个距离数值，数值大小是源点到达该点的最短距离。就像最短路径问题那样子。

每次以最短路径扩充流量之后，最短路径上的点的距离数值并不一定会增加，必须将所有到达该点的最短路径都截断之后，距离数值才会增加。因此这种方式是估计不出结果的。

时间複杂度

以 BFS 寻找 O(VE) 条扩充路径的时间。图的资料结构为 adjacency matrix 的话，便是 O(V^2 * VE) = O(V^3 * E)；图的资料结构为 adjacency lists 的话，通常把 BFS 的时间複杂度 O(V+E)，省略了 V 而写成简单的 O(E)，所以总共是 O(E * VE) = O(V * E^2)。

找出一个最大流＋计算最大流的流量

UVa 820 10330 10779 563 10511 10983

Maximum s-t Flow: Blocking Flow Algorithm（Dinic's Algorithm）

抽刀断水水更流。《李白．宣州谢朓楼饯别校书叔云》

想法

Shortest Augmenting Path Algorithm 的加强版，改为找到一样长的最短扩充路径们。

Admissible Network

剩馀网路上面，以源点（汇点）作为起点，计算源点（汇点）到每一点的最短距离。

剩馀网路上面，一条由源点往汇点方向的边、两端点最短距离相差一，称作“容许边”。所有容许边，整体视作一张图，称作“容许网路”。

容许网路是有向无环图（DAG）、分层图（Layered Graph）。容许网路可以画成一层一层的模样，只有相邻的层有边。

容许网路就是剩馀网路的“最短路径图”。“最短路径图”尚未成为专有名词，“ Next-to-Shortest Path ”稍有提及。

容许网路上面任意一条由源点到汇点的路径，都是最短扩充路径。藉由容许网路，可以很快找到一样长的最短扩充路径们。

Blocking Flow

容许网路上面，一个由源点到汇点的流，无法再扩充流量，称作“阻塞流”，通常有许多种，也不必是最大流。

容许网路上面，逐次找到一样长的最短扩充路径们，并且每次都让扩充的流量到达瓶颈，直到找不到为止；整体形成阻塞流。

剩馀网路上面，以阻塞流扩充流量，就断绝了所有一样长的最短扩充路径。前面章节提到，利用 Vertex Labeling with Shortest Distance 估计不出结果，此处却是使用这个方式。

演算法：找出一个阻塞流

容许网路上面寻找最短扩充路径，不必溯洄冲减。溯洄冲减会增加路径长度，最后得到的不是最短扩充路径。

由源点随意往汇点走，若遇到死胡同，就重头开始走，下次避免再走到死胡同。若顺利走到汇点，就形成一条最短扩充路径，并且扩充流量。

改由汇点随意往源点走，就不会遇到死胡同。

一条最短扩充路径，至少有一条边是瓶颈。容许网路最多只有 E 条边能作为瓶颈，所以一个阻塞流最多只有 E 条最短扩充路径。

从源点走到汇点并扩充流量需时 O(V)，最多有 O(E) 条最短扩充路径，所以找出一个阻塞流的时间複杂度为 O(VE)。

演算法

重覆以下动作最多 V-1 次，直到无法扩充流量：
1. 计算 residual network 上各点离源点（汇点）的最短距离。
2. 建立 admissible network。
3. 寻找 blocking flow，并扩充流量。

时间複杂度

每次找到一个阻塞流并扩充流量之后，容许网路上面，所有由源点到汇点的最短路径都阻塞了；剩馀网路上面，源点到汇点的最短距离会增加（扩充流量而新增的反向边，也不会减少源点到汇点的距离），下次的最短扩充路径会更长。

扩充路径的长度范围是 1 到 V-1（长度为 0 表示源点与汇点重叠），因此最多找 V-1 次阻塞流，就一定没有扩充路径了。

找一个阻塞流需时 O(VE)，最多找 O(V) 次，故总时间複杂度为 O(V^2 * E)。

找出一个最大流＋计算最大流的流量

UVa 10546

延伸阅读：Dynamic Trees

使用“ Link-Cut Tree ”记录容许网路，寻找阻塞流可以加速到 O(ElogV)，整个演算法可以加速到 O(VElogV)。

延伸阅读：MPM Algorithm

http://www.cs.cornell.edu/Courses/cs4820/2013sp/handouts/DinicMPM.pdf

在容许网路上，定义一个节点的容量是 min(所有出边总和，所有入边总和)，容量最小的节点即是瓶颈。找阻塞流时，不断找到扩充路径经过瓶颈（切两段，先往源点找、再往汇点找），使用 Binary Heap 找瓶颈为 O(V^2 * logV)；使用 Fibonacci Heap 找瓶颈为 O(V^2)。找 V 次阻塞流为 O(V^3)。

Maximum s-t Flow: Capacity Scaling Algorithm

演算法

大意是：把容量的数值，由最高位 bit 到最低位 bit，逐一添加到暂存容量的数值尾端。每添加一个 bit，就以暂存容量找一次最大流。过程中持续累计计算的结果。

1. 令 C 为容量上限。C' 为依序添加 bit 的容量上限，一开始设为零。
2. 由 C 的最高位 bit 开始，直到 C 的最低位 bit 为止，不断重複下面动作：
	甲、把 C 的该 bit 添加到 C' 的尾端。
	乙、当前流量成为方才的两倍。
	丙、寻找扩充路径（或扩充流），填满 C' 多出的容量，达到当下的最大流。

时间複杂度

甲、找一条扩充路径为一次 Graph Traversal 的时间。图的资料结构使用 adjacency matrix 为 O(V^2)；图的资料结构使用 adjacency lists 为 O(V+E)，这裡省略 V 写成 O(E)。

乙、每个步骤开始之前，由源点到汇点的剩馀容量都已经填满。在每个步骤当中，添加到图上各条边的容量只有 0 或 1，由源点到汇点的剩馀容量顶多增加 E。也就是说，每个步骤顶多出现 E 条流量为 1 的扩充路径，顶多只能扩充 E 大小的流量，就会达到当下的最大流了。

丙、令一张图的管线容量最大者为 C，一一拿出 bit，所以这个演算法就会有 O(logC) 个步骤，以 2 为底的 log。

由甲乙丙乘积可知，总时间複杂度，依据资料结构的不同，分别为 O(V^2 * E * logC) 与 O(E^2 * logC)。

当 C 不大，会比 Shortest Augmenting Path Algorithm 快，尤其是 Shortest Augmenting Path Algorithm 每次所找到的扩充路径的流量都很小的时候。

计算最大流的流量（adjacency matrix）

Maximum s-t Flow: Preflow, Push, Relabel

壹、push

想像一下：于源点放入足够水量，然后用力推挤源点，就像针筒注射、发射水枪一样，让源点的水一股作气鑽过整个流网路，最后从汇点喷出水流。

受限于流网路的管线容量瓶颈，水流流量是有上限的。水鑽过流网路的路线，就是一个最大流。汇点喷出的水流流量，就是最大流的流量。

然而电脑程式无法直接实现“一股作气鑽过整个流网路”，电脑程式只能一个一个算、一步一步算，所以我们只好一个一个点慢慢推进：首先推进源点的水到其它中继点，再继续推进中继点的水到其他中继点，一个接著一个点慢慢地推进到汇点。

贰、excess 和 overflowing

为了实现“一个接著一个点慢慢地推进”的想法，便定义图上每个点都可以储存水，成了“含水点”，其储存水量称作“含水量”。水被推到点上，得以暂时储存在点上，以后随时可以继续推进。

建立含水点、含水量的系统之后，推进顺序也无所谓了，因为水一直存在、不会消失，就算推歪方向，也可以往回推，回复原始状态。

以“含水点”、“含水量”，设计一套找出最大流的方法：
子、先将源点的含水量设定成无限大。
丑、推进源点的水到图上其他点，慢慢推向汇点，推进顺序可随意。
寅、多馀的水量，会受限于管线容量瓶颈，而留在源点和中继点上。
卯、最后能够推进到汇点的水量，就是最大流的流量。

参、residual capacity

推进的同时也记录管线流量，便可以知道水流流动的情形。管线流量与剩馀容量的概念请参考前面的 Augmenting Path Algorithm 章节。

推进一个点的水，甲、要注意点的含水量，乙、注意管线的剩馀容量，丙、尽量填满管线，营造出针筒注射、发射水枪的效果。

肆、admissible edge

“一个接著一个点慢慢地推进到汇点”，要确保各点的水是确实地推向汇点、聚集在汇点，避免漫无目的来回推进，避免环状推进、不断绕圈圈。因此导入了“水往低处流”的想法。

以“水往低处流”来设计方法、解决问题：
子、推向汇点：源点高、汇点低、其他点排好适当的高低顺序。
丑、由源点漫溢：源点是最高点。
寅、朝汇点聚集：汇点是最低点。
卯、避免绕圈圈：不能推水到一样高的点。只能推水到更低的邻点。

伍、height label

为了实现“水往低处流”的想法，便定义图上每个点都有一个“高度值”，并排好高低顺序，由高往低推进、由源点向汇点推进。

高低顺序有两种安排方式：甲、反转所有边之后，以汇点为起点的最短路径长度，作为高度值。乙、以源点为起点的最短路径长度，取负值（可再加常数变成正值），作为高度值。

採用甲有个好处，因为推进规则可以改成：推进一个点的水，只能到、也只需要到“比此点刚好低一层”的邻点。如此可以让推进规则变得单纯、容易实作，也依旧保持著水往低处流的原则。

排好高低次序，以及改变推进规则后，会出现新麻烦：甲、汇点不是最低点。乙、源点的水可能会推不出去。丙、现在要是推歪方向，就不能往回推了。丁、朝向汇点的管线容量不足时，一个点将会水洩不通。必须寻找其他管线，才能流向汇点。

以下将一一解决这些问题。

陆、source and target

无论是哪一种高低顺序安排方式，都不能保证源点最高、汇点最低。採用甲，可以把源点的高度另设为 V-1，源点就一定比图上其他点高；汇点的高度维持为零，汇点就一定比图上其他点低。V 是图上的点数。

Maximum s-t Flow: Discharge

想法

顺著高低顺序推水是我们的初衷。累积足够水量后，就慢慢往前推动，不要每次都一口气推水到最低处，便可以减少 push 的次数。

Discharge

给定一个含水点，不断使用 Push 和 Relabel 把水排掉，直到没水。
以下是允许进行 Discharge 的条件，确定符合后才得进行 Discharge：
壹、含水点不是源点和汇点。
贰、含水点仍有水。

Maximum s-t Flow: Improved Shortest Augmenting Path Algorithm

注记

此演算法没有广为人知的正式名称。

此演算法为 Ahuja 与 Orlin 于 1991 年发表，论文名称是 Distance-directed augmenting path algorithms for maximum flow and parametric maximum flow problems。该篇论文中同时发表了两个最大流演算法，因此若直接称呼 Distance-directed Augmenting Path Algorithm，会无法准确指出是哪一个演算法。

Ahuja 与 Orlin 后来出版一本网路流的书籍，书上描述此演算法为“Shortest Augmenting Path Algorithm 的改良版”，但是仍未给予一个适切的名称。

演算法

Preflow-Push Algorithm 的加强版。以 DFS 的顺序沿著 admissible edge 行走，当遇到死胡同，就 relabel，并且回溯，寻找其他可以到达汇点的路径。

与 Preflow-Push Algorithm 不同的地方，在于此演算法是找到汇点之后，才沿著扩充路径来扩充流量，而不是逐点推水。

时间複杂度仍是 O(V^2 * E)。

寻找扩充路径，沿著 admissible edge 行走，从源点走到汇点，途中各点的高度显然是逐次减一。缺一不可。

任何一种高度出现了、又完全消失之后，表示源点到汇点往后无法贯通，开始 retreat，可以直接结束演算法。此即 cnt 的功用。

UVa 10983

演算法

引入 blocking flow 的概念。以 backtracking 的顺序而非 DFS 的顺序沿著 admissible edge 行走，寻找扩充流而非扩充路径。

特色是寻找每一点到汇点的阻塞流（水足够时）、也就是寻找局部的阻塞流！每次回溯皆实施 relabel，随时调校局部的最短路径长度！

时间複杂度 O(V^2 * E)。

延伸阅读：height label

有了 height label 的概念之后，我们可以重新审视之前的扩充路径演算法，给予更简洁的解释。

Augmenting Path Algorithm（Ford-Fulkerson Algorithm）
不使用 height label。
随便找扩充路径。

Shortest Augmenting Path Algorithm（Edmonds-Karp Algorithm）
每回合都用 BFS 重新建立 height label，
同时用 BFS 找一条扩充路径。

Blocking Flow Algorithm（Dinic's Algorithm）
每回合都用 BFS 重新建立 height label，
每回合都用多次 DFS 找扩充路径（最后形成阻塞流）。

Improved Shortest Augmenting Path Algorithm
一开始用 BFS 建立 height label（也可以全部设定为零），
每回合都用 DFS 找扩充路径。

摘要

最大流问题只有四个要素：
　甲、容量（Flow Network），甲≥0。
　乙、流量（Flow），甲≥乙≥0。
　丙、剩馀容量（Residual Network），甲减乙、反向乙。
　丁、遵行方向（Admissible Network），丁属于丙：边两端高度差为一。

最大流问题：
　给定甲暨源点汇点，令乙趋近甲，求乙。

最大流演算法：
　以丙的视角看问题，有隙就流。（最大流最小割定理）
　以丁的视角看问题，可以缩短流动路线，加速演算法。

最大流演算法有两大类：
　一、扩充路径法（率先流到汇点）
　Augmenting Path Algorithm          丙上随便找一条扩充路径，不断找。
　(Ford-Fulkerson Algorithm)         O(E*F)

　Shortest Augmenting Path Algo.     丙上 BFS 找一条扩充路径，最多 VE 次。
　(Edmonds-Karp Algorithm)           O(V*E*E)

　Blocking Flow Algorithm            丁上找扩充流，最多 V 次。
　(Dinic's Algorithm)                O(V*V*E)

　Improved Shortest Augmenting       丁上找扩充路径，最多 VE 次。
　Path Algorithm                     O(V*V*E)

　Capacity Scaling Algorithm         限制甲尺度找扩充流，最多 logC 次。
　                                   O(E*E*logC)

　二、预流推进法（率先流离源点）
　Preflow-Push Algorithm             随性推  O(V*V*E)
　Relabel-to-front Algorithm         插队推  O(V*V*V)
　FIFO Preflow-Push Algorithm        FIFO 推  O(V*V*V)
　Highest-Label Preflow-Push Algo.   最高推  O(V*V*V)

Maximum s-t Flow: Orlin's Algorithm

http://jorlin.scripts.mit.edu/Max_flows_in_O(nm)_time.html

目前时间複杂度最低的演算法。使用一些糟糕的手法硬凑出来的，缺乏实务价值。