Question

Feasible s-t Flow（s-t Flow）

“可行流”是符合容量限制的流，流量最低是零，流量最高是最大流流量。“可行流”与“流”的定义完全一样，我们常常省略“可行”两个字。差别在于多了“可行”之后，我们专注于“找到一个流”，而非“流量是多少”。

容量下限（流量下限）

先前只讨论容量上限，未讨论容量下限。容量下限大于零，水流有时无法顺利的从源点流到汇点。

流量是零，也能满足容量下限：幽灵循环水流

一般来说，源点必须流出一些水，以满足容量下限。入情入理。

然而有时候，容量下限形成了环。源点没有流出任何水，也能满足容量下限：建立流量极小的一道水流，不断绕环，以满足容量下限。导致“凭空出现循环水流”的弔诡现象。

因此数学家转为讨论“循环流”，于后面章节“Flow”介绍。

或者，假设容量下限不会形成环。

Minimum s-t Flow

Minimum s-t Flow

“最小流”是流量最小的流。

Minimum Cost Maximum s-t Flow

Minimum Cost Maximum s-t Flow

每一条管线，除了有容量限制，还有成本（费率）。成本可以是正值（付费）、负值（补贴）、零（没事）。水流流过管线，必须考虑费用，儘量减少开销。

一、一段水流流过一条管线的成本：边的流量乘以成本。

二、一道水流从源点到汇点的成本：路径上每一条边，流量乘以成本，求总和。

三、一个流的成本：图上每一条边，流量乘以成本，求总和。

“最小成本最大流”。成本最小的最大流，可能有许多个。

UVa 10594 ICPC 5095 3562

流量是零，也能降低总成本：幽灵循环水流

一般来说，源点必须流出一些水，经过负成本边，形成负成本的扩充路径，以降低总成本。入情入理。

然而有时候，负成本边形成了环。源点没有流出任何水，也能降低成本：建立流量极小的一道水流，不断绕环，以降低总成本。

负成本环，导致“凭空出现循环水流”的弔诡现象。

因此数学家转为讨论“循环流”，于后面章节“Flow”介绍。

或者，我们假设图上没有负成本环。

Minimum Cost Maximum s-t Flow: Cycle Canceling Algorithm

演算法

图上不可有负成本环，避免幽灵循环水流。

一、先找一个最大流。
二、在剩馀网路上，不断找负成本环，建立迴流降低成本。
　　直到找不到负成本环为止，即是最小成本最大流。

在一个最大流当中，建立一条封闭的迴流，不会影响总流量，也不会违反流量守恆的规则，虽然会浪费容量空间，但是有机会减少总成本。事实上可以证明，剩馀网路没有负成本环，即是最小成本最大流，证明省略。

寻找负成本环

有三种方式！

负环：运用 Label Correcting Algorithm。整个演算法过程中，最多出现 C 个负成本环，C 是最大的管线容量上限；时间複杂度为 O(VEC)，是伪多项式时间。

最小环：照理说是最理想的方式，可以较快达到最小成本最大流。然而，求最小环是 NP-complete 问题，时间複杂度是指数时间。

最小平均值环：意外的是个不错的选择。整个演算法过程中，最多出现 O(V * E^2 * logV) 个最小平均值环；时间複杂度为 O(V^2 * E^3 * logV)，是多项式时间。证明省略。

Minimum Cost Maximum s-t Flow: Successive Shortest Path Algorithm

演算法

图上不可有负成本环，避免幽灵循环水流。

仿照 Ford-Fulkerson Algorithm，不断寻找成本最小的扩充路径。证明省略。

一开始没有负成本环，往后就没有负成本环。

一、一开始的剩馀网路没有负成本环。

二、成本最小的扩充路径，扩充之后让剩馀网路增加了逆向边（成本随之变号，增加了负成本边），但是剩馀网路仍旧没有负成本环。证明省略。

如此一来，可以确保剩馀网路随时都能实施最短路径演算法。

寻找成本最小的扩充路径

溯洄冲减后，剩馀网路多出许多逆向的负成本边，因此必须採用允许负边的最短路径演算法，例如 Label Correcting Algorithm、Floyd-Warshall Algorithm。

或者利用 Johnson's Algorithm 的调整权重手法，将负边调整为非负边。此时成本最小的扩充路径就会变成零成本边，扩充之后的剩馀网路，就不会多出逆向的负成本边，而是多出逆向的零成本边！如此一来，就可採用不允许负边的 Dijkstra's Algorithm，降低时间複杂度。

一开始图上可能有负成本边，预先实施一次 Label Correcting Algorithm 调整权重，往后就可持续使用 Dijkstra's Algorithm 了。每次实施 Dijkstra's Algorithm 之后，就马上调整权重。

一、用 Label Correcting Algorithm 调整权重，让每条边的成本为非负值。
二、不断寻找成本最小的扩充路径，直到找不到为止：
　甲、用 Dijkstra's Algorithm 寻找成本最小的扩充路径。
　乙、调整权重，让每条边的成本为非负值。
　丙、扩充流量。

找一条扩充路径需时 O(V^2)，最多找 O(F) 条，时间複杂度为 O(V^2 * F)，是伪多项式时间。

找出一个最小成本最大流＋流量＋成本

Minimum Cost Maximum s-t Flow: Primal-Dual Algorithm

演算法

图上不可有负成本环，避免幽灵循环水流。

仿照 Blocking Flow Algorithm，每回合找到全部的成本最小的扩充路径。

利用最短路径长度，调整图上所有边的权重成为非负数之后，此时最短路径上的边就是零成本边。在零成本边所构成的图当中，找最大流，便可以一次找到全部的成本最小的扩充路径。

时间複杂度我也不知道。

Flow

注记

Flow 与 s-t Flow 是两个不同的概念。然而古代人当初定义问题时，却将两者都称作 Flow，从此之后便混淆不清了。

Cut 与 s-t Cut 亦有类似情况。古代人当初没有 Cut 的概念，将 s-t Cut 直接称作 Cut。不过自从有人发表 Cut 的演算法之后，众人便开始注重用词了。

以下章节，Flow 译作“流”或“循环流”，s-t Flow 译作“源汇流”。

Flow

从现在起，水流不再从源点流到汇点，水流改为不断循环。

要计算总流量，可将水流分解成数个环，以环流量的总和作为总流量。每次挑一条有水流的边开始寻找环，最多分解成 E 个环。

Supply / Demand

“供点”有水注入、“需点”有水洩出，彷彿源点与汇点。图上可以有多个供点与需点，供水量总和必须等于需水量总和，才有机会形成可行流。

图上每一点皆有供需水量：supply 的供需水量为正值，该点流出多于流入；demand 的供需水量为负值，该点流入多于流出；其他的点的供需水量为零，流入等于流出。

供需水量 = 流出水量 - 流入水量

导入 supply 与 demand 之后，总流量的定义就不明确了。这裡姑且定义成：supply 的总和，再加上不受 supply 与 demand 影响的循环流流量。

最大流最小割定理、可行流定理

导入水流流量：任意一个割，甲侧流往乙侧的水量总和，等于乙侧流往甲侧的水量总和。

导入容量上限：任意一个割，甲侧流往乙侧的水量总和，小于等于甲侧到乙侧的容量总和。最大流流量，小于等于任何一个“管线容量的最小 s-t 割”！

导入供需水量：任意一个割，甲侧的供需水量总和，必须小于等于甲侧到乙侧的容量总和，才能形成可行流。

导入容量下限：任意一个割，甲侧到乙侧的容量下限总和，必须小于等于甲侧到乙侧的容量上限总和、也要小于等于乙侧到甲侧的容量上限总和，才能形成可行流。

容量下限变成零

有向边的容量下限，得移转至 supply 与 demand。

预先流水，水量等于容量下限：

必须记录每条边的预流水量与耗费成本，以利之后还原。

容量上限变成无限大

其实没有必要移除容量上限──最大流演算法皆支援容量上限。不过还是介绍一下吧。

移除容量下限后，可以进一步移除容量上限。容量上限添加至终点，然后回冲：

移除容量上限后，变成二分图，得以设计更简洁的资料结构与演算法。

负成本变成正成本

运用溯洄冲减，可以把负成本变成正成本。

预先流水，水量等于容量上限：

必须记录每条边的预流水量和耗费成本，以利之后还原。

无向边变成有向边

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

成本非负、没有容量下限：为了降低成本，来回水流可以变成单向水流。上述两条方向相反的有向边，大可不必共用容量上限，宛如普通的有向边。

成本非负、拥有容量下限：预先在无向边上来回流动，满足容量下限。流量是容量下限的一半，可以是 0.5。如果流量只能是整数，则可以类比为 0/1 Knapsack Problem，属于 NP-complete 问题。

成本为负：同上。流量是实数，就来回流动。流量是整数，NP-Complete。

归约

Feasible s-t Flow -> Feasible Flow -> Maximum s-t Flow
导入成本，依然如此。

可行源汇流化作可行循环流。汇点到源点增加一条管线，容量上限无限大（图上所有边的容量上限总和），成本无限小。

可行循环流化作最大源汇流。新增源点与汇点，源点接至 supply，容量上限为供水量；demand 接至汇点，容量上限为需水量。然后尝试求最大源汇流，若源点管线与汇点管线皆满溢，则有可行循环流，反之则无。拆除新增管线，最大源汇流就变成可行循环流。

总结

流的问题总是可以简化成：有容量上限、无容量下限、成本非负、有向边，许多 supply 和 demand。

无论流动方式是循环流、源汇流，无论最佳化目标是最大流、最小流、可行流，都可以归约成 Minimum Cost Maximum s-t Flow。

UVa 11647 1259 ICPC 3787 4722 5131

Feasible Flow

“可行流”。符合供需水量、容量上下限的流。

直觉的方式，就是归约。进阶的方式，就是瞭解归约过程之后，直接以原图实施计算，不归约、不改图。

承袭 Maximum s-t Flow 演算法，额外考虑 flow、supply、demand 等新概念。

不断寻找起点为 supply、终点为 demand 的扩充路径，进行扩充后就根据水量减损 supply、增益 demand，直到图上没有 supply 与 demand 为止。

Maximum Flow

“最大流”。流量最大的可行流。

一、首先随便找出一个可行流，然后不断找扩充环。

根据最大流最小割定理，剩馀网路没有扩充环，即是最大流。

二、穷举所有两点之间容量 s-t 割，取最小值。【尚待确认】

Minimum Flow

“最小流”。流量最小的可行流。

一、坚持使用扩充路径而不是扩充走道，即得最小流。【尚待确认】

二、首先随便找出一个可行流，然后不断消去扩充环。【尚待确认】

我找不到任何有关最小流的正确性证明！

Minimum Cost Flow

“最小成本流”。成本最小的可行流。

承袭 Minimum Cost Maximum s-t Flow 演算法。

Cycle Canceling Algorithm：先找到任意一个可行流，再以负成本环进行扩充。

Successive Shortest Path Algorithm 与 Primal-Dual Algorithm：不断寻找起点为 excess、终点为 deflict、成本最小的扩充路径，直到所有 excess 与 deflict 成为零。如果 excess 与 deflict 没有同时成为零，则没有可行流。

Excess / Deficit

“馀水点”水量超出平衡，“缺水点”水量低于平衡。当图上有 excess 与 deficit，表示流量不平衡，不是可行流。

馀缺水量 = 当前流入水量 - 当前流出水量 + 供需水量 

Multi-commodity Flow

k Vertex-disjoint Paths
k Edge-disjoint Paths

给定 k 组起点与终点，找齐 k 条路径，点（边）皆相异；除了起点与终点。可能找不到。

Flow 问题，源点与汇点不必对应，P 问题。

此问题，起点与终点必须对应，NP-complete 问题。

差别在于交叉路径。Flow 问题，运用溯洄冲减，交叉路径总是变成不交叉路径。此问题则不然。

UVa 11301

k Vertex-disjoint s-t Paths
k Edge-disjoint s-t Paths

给定一组起点与终点，找出 k 条路径，点（边）皆相异；除了起点与终点。起点都是同一点、终点都是同一点，无所谓对不对应。可能找不到。

解法是 Maximum s-t Flow。

UVa 10806 ICPC 4259 4271

进阶版本，这 k 条路径的权重总和必须最小。

解法是 Minimum Cost Maximum s-t Flow。

UVa 11823 1236 ICPC 3570

Multi-commodity Flow

指定多组供点、需点，必须对应。

流量是实数，P 问题。流量是整数，NP-Complete 问题，大家改为研究速度飞快的近似演算法。

http://arxiv.org/pdf/1304.2338v1.pdf

http://www.cs.berkeley.edu/~vazirani/pubs/partitioning.pdf

源汇流必须避免幽灵循环水流，限制图上没有容量下限环、没有负成本环。为求方便，大家习惯讨论循环流。