Be water, be Flow 如水，如流

What is 网络流？ 我们先来看看定义， 网络流是一个有条件的有向图G=(V, E)，满足以下条件： - 一个源点（source），即入度为0的起始点 - 一个汇点（sink），即出度为0的终点 - 容量（capacity），即每条管道的最大可承载的水量 - 流量（flow），即每条管道真实流动的水量

在流动的过程中有两个自然法则： - 容量限制（Capacity constraint）：每条水管的水流不得超过这条水管的最大容量, 即f(u,v) <= c(u,v) - 流量守恒（Flow conservation）：除了水源和汇点，其他中间节点都不能凭空产生或消耗水

上面是网络流的定义，我们可以联想为城市的水路系统，源点就是水源；节点就是分流的水闸，自然没有存储与消耗生产水的能力；管道有最大容量，流量就是管道里真实流动的水量；汇点就是城市。

作为人类，我们天然有着想要最多的趋向，管道修好了后，大小与位置是难以改变的，闸门作为节点也是，那我们要怎么知道当下的流动策略是不是最大，如果不是，要怎么优化呢？

--- 给我最大的水流！ 我们往往想要最大化汇点可以接受到的流量，那么我们如何知道一个当前的网络流是否是最优流法呢？

我们面对这类具象的问题时，可以从绝对的存量出发，设置衡量标准的数据（这里就是流（flow），即从源点出发的水流总量或者到达汇点的水流总量，两者相等），然后比较；也可以从相对的变量出发，这个时候我们要判断的是当下能不能更大，更优，这是从变的角度出发，颇有差分数组的精妙。

于是我们引入残量网络—关于变的网络流

--- Residual graph 残量网络——以变视之，万物易之 残量网络可以理解为 重生之我在异世界改变，这一次我要拿下最大的流量 帮助我们判断是否可以再往里面加入更大流的辅助图。

图的建立相当简单，我们将原图存量的边站在变量的角度看，一条容量为c，当下流量为f的管道，可以变化的方式有哪些？

要么增加，要么回撤，要么不变。 对于前者，可以增加的最大值是c-f, 即管道的容量减去当下的流量。 对于后者，可以回撤的最大的值就是当下全部的流量f。 那么现在一条 u-v with f 流量的单向边可以从变的角度理解为可最大增加 u-v with c-f 和 最大回撤v-u with f 的双向边。权重为0意味着是已经max了，在变的角度这个方向是死路。

遍历每一条边并站在变化的角度重构理解，就是我们·的残量网络。 既然我们有了关于变的图，我们只需判断能不能找到从source到sink的valid的一条路径就可以了，如果可以，意味着我们就有调度变化的余地，没有则意味着已经为最优解。基于残量网络而寻找到由soucre到sink的valid的path就叫增广路径。

--- Argument path 增广路径——能有活水源头来

增广路径是在以source为起点，sink为终点，自source开始BFS或DFS遍历得到valid的路径，它可以由正向的增强边和反向的回撤边组成，代表着在原有网络流的基础上可以继续通水的路径。

那么这条path的可以送的活水最大流量是多少呢？ 对，就是这条path里最小的容量（Bottleneck），Pretty straightforward!

那么我们成功找到了活水路径，现在开始注入活水，我们更新残量网络：沿着这条路径，对于每条双向边的正向边，我们减去bottleneck的值，反向边就加上相同的值（意味着这条边可增加的流量减少了—因为已经化作活水了，可回撤的增加了—因为更新后的流量变多了）。

update后我们继续寻找路径，然后重复直到我们找不到path，此时即为最优的网路流的残量网络。最后我们就按残量网络里每条边的反向边权重更新最初的网络流的权重就可以。

这里稍微插一嘴代码的实现，关于正向边和反向边，我们会利用到异或建边法。

在计算机底层，偶数和它相邻的奇数可以通过与1异或的方式互相转化。与1即0b0001异或，会将数字二进制的最后一位的1转化为0，0转化为1，从而实现简易的转换（在硬件上我们只需要一个逻辑门（XOR门））。

pseudocode会如此： edge[i].capacity -= value edge[i ^ 1].capacity += value

--- Ford-Fulkerson 算法——FF 算法 Ford-Fulkerson 算法（简称 FF 算法）其实就是我们刚才推演的整个过程的正式学术表达。

在算法竞赛和工程界，我们通常说 FF 算法是一个“方法（Method）”，而不是一个具体的“算法”，因为它只给出了核心思想，但没有规定你到底用什么方式（DFS 还是 BFS）去找增广路径。

- 初始化： 将所有边的初始流量设为 0（在代码里就是建立正反向边，反向边容量设为 0）。 - 循环寻找： 在当前的残量网络中，寻找一条从源点 S 到汇点 T 的增广路径。 - 增广更新：找出这条路径上的瓶颈容量 delta。将路径上所有正向边的残量减去delta。将路径上所有反向边的残量加上delta。 - 终止： 当残量网络中再也找不到任何一条增广路径时，算法结束。当前的流量就是最大流。

FF算法虽然逻辑优美，但是效率存在隐患 时间复杂度（Pseudo-polynomial time）：每次寻找增广路 (比如用 DFS) 需要 O（|E|）的时间，最多可能需要找 |f| 次 ( |f|是最大流的值)。因此时间复杂度为 O(|f||E|)。

如果网络的边容量极其巨大（比如 1,000,000），且算法“运气很差”，每次都选了一条只增加 1 个单位流量的“奇葩”增广路（极端反例），算法就会在两个节点之间来回“撤销-注入”一百万次。此时的时间复杂度会随着容量指数级退化。

后面我们会引入更优的算法。

--- Max-flow, Min-cut Theorem 最大流，最小切

切（cut）的定义如上所示，切的capacity是只考虑从S到T的方向边的capacity的总和，切的flow就是S到T的流总量减去T到S的流总量。

我们易得切的flow小于等于切的capacity，即f (S, T ) ≤c(S, T ) 所以 |f |≤c(S, T )。

这在证明FFA的正确性的时候会用的： Let f be a flow. Recall that the value |f |is at most the capacity of any cut c(S, T ). ▶ Thus, if we find a flow f which equals the capacity of some cut (S, T ), then such flow must be maximum and the capacity of such a cut must be minimum. ▶ We now show that when the Ford-Fulkerson algorithm terminates, it produces a flow equal to the capacity of an appropriately defined cut.

简而言之，max-flow是尽力而为，min-cut是物理极限 在计算机科学和图论中，最大流的值必定等于最小割的容量。

我们之所以无法再多送哪怕一滴水（达到最大流），唯一的原因就是这滴水必然会被网络中那几根最窄、最关键的管子（最小割）给堵死。

水流之绵长，见于心胸之宽广。

---

“上帝视角”的资源调度

我们来看看网络流的应用 核心问题：资源的有条件限量分配（二分图最大匹配）

漫展上开了一个初音未来 (Hatsune Miku) 的周边快闪店。店里有 k 种不同的周边（吧唧、海报、手办等），每种的实际库存量是 mj。现在店外排了 n 个二次元同好，每个人心里都有一个特定的“必买清单”。为了防黄牛规定：每人最多只能买 5 件不同的周边。问能最多卖掉多少？

对于这种 我们就可以使用网络流来降维打击： 超级源点 -顾客：连一条容量为 5 的水管。这保证了无论如何，没人能从源头抽走超过 5 件商品。

顾客 -周边：如果某人想买某件周边，连一条容量为 1 的水管。容量是 1 意味着同一种周边每人只能拿一件。 周边 - 超级汇点：连一条容量为 mj（真实库存）的水管。这保证了不管多少人想买，卖出的总数绝对不会超过库存。

只要让水流穿过这个网络，流进汇点的最大水量，就是能卖出的最多周边数量，而且这套方案保证了不会超卖，灰常nice啊。

抽象建模的话就是二分图（Bipartite graph）

二分图的定义：在图论中，二分图是一类特殊的图，又称为二部图、偶图、双分图。二分图的顶点可以分成两个互斥的独立集 U 和 V 的图，使得所有边都是连结一个 U 中的点和一个 V 中的点。顶点集 U、V 被称为是图的两个部分。等价的，二分图可以被定义成图中所有的环都有偶数个顶点）

二分图描述的是两种事物之间的映射关系，那么我们加入源点和汇点，同时通过容量来代表限制条件，就可以很好地解决上述这类问题。

---

总结——The flow tells. 1. 系统的上限，永远由它最薄弱的瓶颈决定。（最大流最小割定理） 你设计再复杂的调度方案，最终的吞吐量、并发数或总收益，都死死卡在系统最窄的那道“割（Cut）”上。解决问题的核心从来不是盲目在全局发力，而是精准找到并突破那个“最小割”。 “打蛇打七寸”，治事看命门。

2. 局部最优的堆砌，必然通向全局的死局。（残量网络的意义） 凭借直觉的“贪心”（看到有路就猛走）往往会抢占关键通道，堵死未来的可能性。真正高维的优化策略，不在于每一步都赚得最多，而在于永远保留“撤销和纠错（反向边）”的机制。所谓残量网络，就是算法世界的“后悔药”。

3. 一切现实法则，皆可“降维”为拓扑限制。 物理空间的距离、金融资产的配额、电影库存的数量、微服务的互斥锁……现实世界里看似千奇百怪的“约束条件”，在数学维度上，都可以抽象为一条线段（边）以及上面的一个数字（容量）。

4. 最优解不是“找”出来的，而是“流”出来的。 面对错综复杂的多对多资源分配（如婚介匹配、跨国物流、芯片布线），不要试图用人脑去写无穷无尽的 if-else 规则。划好红线（容量），连好管道（拓扑），打开水龙头（跑最大流算法），水自然流过的痕迹，就是无懈可击的最优分配方案。

网络流，就是一本《在极度受限的复杂规则下，如何使用好每一滴资源、逼近全局利用率极限的数学指导手册》。

Be water, my friend.