欢迎来到网络流（Flows in Networks）！
在本章中，我们将学习如何管理系统中的“流量”。无论是管道中的水流、互联网上的数据，还是高速公路上的车辆，目标都是一样的：如何在不弄垮系统的前提下，将最多的资源从起点运输到终点？
这是决策数学 2（Decision Mathematics 2）的核心部分。一旦你掌握了“标记法（labelling）”的节奏，你会发现这其实很有成就感。如果一开始看到满屏的箭头和数字觉得很混乱，别担心——我们会一步步拆解它！
1. 网络的解剖
在我们开始处理流量之前，必须先了解我们面对的是什么。在本课程大纲中，我们只处理有向弧（directed arcs）（即显示流动方向的箭头）。
- 源点（Source, S）：流动的起点（就像“水龙头”）。
- 汇点（Sink, T）：流动的终点（就像“排水口”）。
- 容量（Capacity）：一条弧所能承载的最大流量。你可以把它想象成管道的粗细。
- 可行流（Feasible Flow）：必须遵循两条规则的流动：
1. 不超过任何弧的容量。
2. 流量守恒（Conservation of Flow）：流入顶点的流量必须等于流出的流量（源点和汇点除外）。
小复习：如果有 10 公升的水流进一个交汇点，就必须有 10 公升流出。你不能让水在网络中间凭空消失！
2. 割（Cuts）及其容量
割（Cut）就像是一条虚拟的线，将源点与汇点完全隔开。如果你“切断”这些被割穿过的弧，流动就无法到达终点。
如何计算割的容量
要找到割的容量，你只需将所有从源点那一侧指向汇点那一侧的弧的容量加起来即可。
常见错误：如果一条弧是从“汇点侧”往“源点侧”（即反方向）穿过割线，我们必须忽略它的容量。我们只关心那些有助于流量到达汇点的部分！
重点总结：割的容量 = \(\sum (\text{所有从源点侧指向汇点侧的弧的容量})\)。
3. 标记程序（The Labelling Procedure）
这是本章的“重头戏”。我们利用这个程序来增广（augment）（增加）流量，直到找到最大可能流量为止。想象一下，你现在有一个半满的管道系统；这个程序能帮你找到那些“缝隙”，从而塞入更多的流量。
两个箭头
在每一条弧上，我们使用包含两个数字和两个箭头的标记：
- 前向箭头（\(\rightarrow\)）：显示我们还能增加多少流量。计算方式为 \(\text{容量} - \text{当前流量}\)。
- 后向箭头（\(\leftarrow\)）：显示我们可以“移除”或重新导向多少流量。这单纯等于 \(\text{当前流量}\)。
增广步骤
- 寻找路径：寻找任何一条从 S 到 T 的路径，且路径上所有的“前向箭头”数值都大于零。
- 确定增加量：找出该路径上最小的前向箭头数值。我们称这个值为 \(x\)。
- 更新标记：
- 对于路径上的每一条弧，从前向箭头中减去 \(x\)。
- 对于路径上的每一条弧，在后向箭头上加上 \(x\)。 - 重复：持续进行上述步骤，直到没有任何从 S 到 T 且具备“前向空间”的路径为止。
你知道吗？即使一条弧在某个方向看起来已经“满了”，你偶尔也可以通过后向箭头“推回”流量，从而开辟出一条更好的路径！
4. 最大流最小割定理（Max-Flow Min-Cut Theorem）
这是决策数学中一个著名的规则，它指出：
网络中的最大流（Maximum Flow）等于最小割（Minimum Cut）的容量。
如果你找到了一个流量（使用标记程序），并且发现刚好有一个割的容量值与之相等，那么你就已经证明了你的流量就是该网络的最大流量。
重点总结：要证明你找到了最大流，试着找出网络中的“瓶颈”。那个瓶颈就是你的最小割。
5. 处理变化题型
有时考题会给你一个“混乱”的网络。以下是整理它们的方法：
多个源点与汇点（3.4）
如果你有三个工厂（源点）和两个商店（汇点），别慌！
- 创建一个超级源点（Super-Source），并画弧线连接到原本的源点。这些新弧的容量就是工厂能产出的总容量。
- 同样地，创建一个超级汇点（Super-Sink），并将原本的汇点连接到它。
顶点容量限制（3.4）
有时一个交汇点（顶点）只能处理一定量的流量（例如：一个抽水站一次只能处理 50 个单位）。
技巧：将该顶点一分为二！顶点 \(V\) 变成 \(V_{in}\) 和 \(V_{out}\)。用一条容量等于该顶点限制值的弧将它们连接起来。
类比：想象一家夜店。顶点就是门口。要模拟门口的容量，你必须从“门外”(\(V_{in}\)) 通过“身份查验”（容量弧）进入“店内”(\(V_{out}\))。
6. 下限容量（3.5）
在大多数问题中，流量的下限是零。但有时一条弧必须承载一定的最低流量（即下限容量）。
在这些情况下，弧上的流量 \(f\) 必须满足：
\(\text{下限容量} \leq f \leq \text{上限容量}\)
在检查“可行流”时，你必须确保每一条弧都维持在其特定的边界之内。
常见错误提示
- “反向”割：在计算割的容量时，错误地加总了指向源点侧的弧。千万别这样做！
- 算术错误：在增广标记时，加减法非常容易出错。进行增广时请务必反复检查你的减法运算。
- 漏掉路径：请务必仔细扫描整个网络。有时候，包含“后向箭头”的路径反而是达到最大流量的唯一途径。
最后鼓励：决策数学的重点在于遵循算法。保持你的图表清晰，使用铅笔以便随时擦掉错误的标记，并记住黄金法则：流入 = 流出！ 你一定做得到的！