网络流简介
欢迎来到网络流 (Network Flows) 的世界！这一章的核心在于如何最高效地将“物资”从一个地方传送到另一个地方——无论是水管中的水、互联网上的数据，还是道路上的车流。如果你曾经好奇城市是如何管理交通，或者 Netflix 是如何同时向数百万人串流播放电影而不令系统崩溃的，那你其实已经在思考网络流的问题了。
如果起初觉得这些概念有点抽象，请别担心！我们会将其拆解为简单的步骤，并运用大量的比喻来帮助你想象其中的运作机制。学完这一章，你就会成为找出任何系统中“瓶颈 (bottlenecks)”的专家！
1. 基本概念：节点、弧与容量
在开始分析流动之前，我们需要先认识地图上的各个组成部分。在离散数学中，我们将这张地图称为网络 (network)（或有向图）。
节点 (Nodes，或称顶点 Vertices)： 这些是图中的圆圈或点，可以想象成路口或城市。
弧 (Arcs，或称边 Edges)： 这是连接节点的线。在这一章中，它们总是有箭头的，因此称为有向弧 (directed arcs)。可以想象成单行道。
源点 (Source, S)： 流动的起点。可以想象成“水塔”或“工厂”。
汇点 (Sink, T)： 流动的终点。可以想象成“住家”或“客户”。
容量 (Capacity)： 每一条弧都有一个上限，代表该路径能通过的“物资”最大量。我们通常会在弧的旁边标注这个数值。
黄金法则：流守恒定律 (Conservation of Flow)
对于除源点和汇点外的每一个节点，进入该节点的总流量必须等于离开该节点的总流量。你不可能让水在管道系统的中途凭空消失！
快速重温：关键术语
源点 (S)： 起点。
汇点 (T)： 终点。
容量： 弧的流量上限。
流量 (Flow)： 当前通过该弧的实际数量（流量 \( \le \) 容量）。
2. 理解割集 (Cuts)
想象你想通过“切断”某些管道来完全阻断从源点到汇点的流动。割集 (cut) 是一条线，它将节点划分为两个集合：一个集合包含源点，另一个包含汇点。
割集的值 (Value of a Cut)：
割集的值等于所有从“源点侧”指向“汇点侧”的弧的容量之和。
重要提示： 如果某条弧是“反向”的（即从汇点侧指向源点侧），我们在计算割集值时会忽略它的容量。我们只关心那些试图穿过“缺口”前往终点的流量。
你知道吗？
任何割集的值总是大于或等于实际流量的值。如果你找到一个值为 50 的割集，你就能肯定流量绝对不可能高于 50。
3. 最大流最小割定理 (Maximum Flow-Minimum Cut Theorem)
这是本章最重要的定理。它指出在任何网络中：
\( \text{最大流} = \text{最小割的值} \)
比喻：链条与最弱的一环
将网络想象成一连串的链条。整个系统所能承受的最大重量取决于其最弱的一环。“最小割”就是数学上找出整个网络中最终瓶颈的方法。
关键重点
如果你被要求证明某个流量是最大流，只需找到一个割集，其值等于该流量。如果两者相等，你就成功找到了极限！
4. 超级源点与超级汇点
有时候题目会出现多个工厂（源点）或多个客户（汇点）。这看起来很复杂，但有一个巧妙的解决方案：使用超级源点 (Supersources) 和超级汇点 (Supersinks)。
1. 创建一个单一的“超级”节点。
2. 使用无限容量（或等于总供应量/需求量的容量）的弧，将它连接到所有原始的源点（或汇点）。
3. 现在，你可以将此问题视为一个只有单一起点和单一终点的标准网络来处理。
5. 增广路径 (Augmenting Flows)：如何达到最大值
为了找到最大流，我们使用一个称为增广 (augmenting) 的过程。这意味着“增加流量”。
逐步指南：
1. 从零流量开始。
2. 寻找一条从 S 到 T 的路径，且该路径上每一条弧都有剩余容量。
3. 找出该路径上的瓶颈（剩余容量最小的弧）。我们称此值为 \( x \)。
4. 将该路径上每一条弧的流量增加 \( x \)。
5. 重复此过程，直到从 S 到 T 再也没有具备剩余容量的路径为止。
常见错误： 千万别忘了更新过程中的剩余容量！如果一根管子的容量是 10，你通过了 4 个单位，那么它以后就只剩下 6 个单位的容量可用。
6. 进阶限制：上限与下限容量
在现实世界中，情况会复杂一些。
上限容量 (Upper Capacities)： 这是我们一直使用的——即最大限制。
下限容量 (Lower Capacities)： 有时候某条弧必须运载至少一定数量的流量。例如，发电厂可能需要向变电站输送最低限度的电力以维持运作。
要解决这类问题，我们需要检查是否存在一个同时满足最低需求和最大限制的“可行流 (feasible flow)”。如果你觉得这很棘手，可以把它想象成在开始寻找额外空间之前，先将管子“预载”上所需的最低流量。
7. 节点容量
如果路口本身就是瓶颈怎么办？想象一个火车站，即使连接它的轨道能容纳 1,000 名乘客，但车站本身每小时只能处理 500 名乘客。
技巧：节点分裂 (Node Splitting)
为了模拟具有容量限制的节点，我们将节点“分裂”为两个由单一弧连接的节点。
1. 将节点 A 变为 A-in 和 A-out。
2. 所有进入 A 的弧现在改为进入 A-in。
3. 所有离开 A 的弧现在改为从 A-out 离开。
4. 创建一条从 A-in 到 A-out 的新弧，并将其容量设为该节点的容量限制。
现在，节点的限制就变成了另一条弧的容量，我们可以使用标准方法来求解了！
快速重温：常见陷阱
- 方向很重要： 在计算割集时，只统计从源点侧指向汇点侧的弧容量。
- 瓶颈： 路径的总流量受限于该路径上最弱的弧，而不是所有弧的总和。
- 守恒： 最终检查时，务必确认所有节点都符合“流入量 = 流出量”。
章节总结
网络流是解决优化问题的强大工具。你已经学会了如何使用有向弧来呈现系统，如何透过割集识别瓶颈，以及如何使用最大流最小割定理来证明你找到了最佳解。无论你是处理超级源点还是受限的节点容量，核心原则始终如一：持续增加流量，直到达到极限为止！