算法（H）笔记——最大流
本文最后更新于 2026年7月8日 20:26:29
最大流
流的定义
设 \(G=(V,E)\) 为一个流网络，其容量函数为 \(c\)。设 \(s\) 为网络源点，\(t\) 为汇点。
\(G\) 中的流是一个实值函数：
\[ f: V \times V \to \mathbb{R} \]
它满足下面两个性质。
容量限制
对于所有结点 \(u,v \in V\)，要求：
\[ 0 \le f(u,v) \le c(u,v) \]
也就是说，一条边上的流量不能为负，也不能超过这条边的容量。
流量守恒
对于所有结点 \(u \in V-\{s,t\}\)，要求：
\[ \sum_{v \in V} f(v,u) = \sum_{v \in V} f(u,v) \]
也就是说，对于非源点、非汇点的中间结点，流入量等于流出量。
无边时的流量
当 \((u,v) \notin E\) 时，从结点 \(u\) 到结点 \(v\) 的流量为：
\[ f(u,v)=0 \]
流的值
流 \(f\) 的值 \(|f|\) 定义为从源点 \(s\) 流出的总流量减去流入源点 \(s\) 的总流量：
\[ |f|=\sum_{v \in V} f(s,v)-\sum_{v \in V} f(v,s) \]
直观理解：最大流问题就是希望让从源点 \(s\) 到汇点 \(t\) 的总流量尽可能大。
残存网络
设有一个流网络 \(G=(V,E)\)，其源点为 \(s\)，汇点为 \(t\)。设 \(f\) 为图 \(G\) 中的一个流。
对于结点对 \(u,v \in V\)，定义残存容量 \(c_f(u,v)\) 为：
\[ c_f(u,v)= \begin{cases} c(u,v)-f(u,v), & \text{若 } (u,v) \in E \\ f(v,u), & \text{若 } (v,u) \in E \\ 0, & \text{其他} \end{cases} \]
含义：
- 若原图中存在边 \((u,v)\)，则这条边还能继续增加的流量是 \(c(u,v)-f(u,v)\)。
- 若原图中存在反向边 \((v,u)\)，则可以沿反方向撤回的流量是 \(f(v,u)\)。
- 若两者都不存在，则残存容量为 \(0\)。
残存网络用于描述：在当前流 \(f\) 的基础上，哪些方向还可以继续调整流量。
切割与最小切割
网络 \(G=(V,E)\) 中的一个切割 \((S,T)\)，是将结点集合 \(V\) 划分为两个集合 \(S\) 和 \(T=V-S\)，并满足：
\[ s \in S, \quad t \in T \]
也就是说，切割必须把源点和汇点分到两边。
横跨切割的净流量
若 \(f\) 是一个流，则定义横跨切割 \((S,T)\) 的净流量为：
\[ f(S,T)=\sum_{u \in S}\sum_{v \in T} f(u,v)-\sum_{u \in S}\sum_{v \in T} f(v,u) \]
含义：从 \(S\) 流向 \(T\) 的总流量，减去从 \(T\) 流回 \(S\) 的总流量。
切割的容量
切割 \((S,T)\) 的容量定义为：
\[ c(S,T)=\sum_{u \in S}\sum_{v \in T} c(u,v) \]
即所有从 \(S\) 指向 \(T\) 的边的容量之和。
一个网络的最小切割，就是整个网络中容量最小的切割。
关键性质
引理 26.4
设 \(f\) 为流网络 \(G\) 的一个流，该流网络的源点为 \(s\)，汇点为 \(t\)。
若 \((S,T)\) 是流网络 \(G\) 的任意切割，则横跨切割 \((S,T)\) 的净流量等于流的值：
\[ f(S,T)=|f| \]
推论 26.5
流网络 \(G\) 中任意流 \(f\) 的值不能超过 \(G\) 的任意切割的容量：
\[ |f| \le c(S,T) \]
含义：任何一个切割都给出了最大流的一个上界。
定理 26.6：最大流最小切割定理
设 \(f\) 为流网络 \(G=(V,E)\) 中的一个流，该流网络的源点为 \(s\)，汇点为 \(t\)。下面三个条件是等价的：
- \(f\) 是 \(G\) 的一个最大流。
- 残存网络 \(G_f\) 不包含任何增广路径。
- \(|f|=c(S,T)\)，其中 \((S,T)\) 是流网络 \(G\) 的某个切割。
直观理解：
- 如果残存网络中还有增广路径，就还能继续增加流量，所以当前流不是最大流。
- 如果已经没有增广路径，则当前流已经达到最大。
- 最大流的值等于某个最小切割的容量。
课堂备注
板书上的方法比教材上的写法更简化，主要过程可以理解为：
- 从当前流出发，构造残存网络。
- 在残存网络中寻找从 \(s\) 到 \(t\) 的增广路径。
- 沿增广路径增加流量。
- 若找不到增广路径，则当前流就是最大流。
- 此时可以由残存网络得到对应的最小切割。
二分图最大匹配
- 增加s和t
额外内容
淘汰赛
flowchart LR
s((s))
AB[比赛 AB<br/>容量 2]
AC[比赛 AC<br/>容量 3]
BC[比赛 BC<br/>容量 4]
A[队伍 A<br/>最多再赢 1]
B[队伍 B<br/>最多再赢 4]
C[队伍 C<br/>最多再赢 6]
t((t))
s -->|2| AB
s -->|3| AC
s -->|4| BC
AB -->|∞| A
AB -->|∞| B
AC -->|∞| A
AC -->|∞| C
BC -->|∞| B
BC -->|∞| C
A -->|1| t
B -->|4| t
C -->|6| t
10:30的板书？0612
左边是将最短路转换成线性规划，右边是将最大流转换成线性规划
- 最短路：最大化每个点的d；约束：I 源点d=0 II 其他用线段长度+三角不等式限制
- 从下往上顶，去找到最短路
两个算法的证明与分析
47一定不行，因为NY和BALL之间有五场比赛要打，一个75一个71，打完至少一个为76>47+28=75
不能只看总和