学习心得 - 算法 - 网络流

ExFish · 2025-06-04 16:59:50 · 算法·理论

建议查看续集。

定义

• 网络（一个特殊有向图）：
  1. 边权变为了流量（容量）记作 \text{c}(u,v)，注意当 u 与 v 之间没有直接连边，那么 \text{c}(u,v)=0。
  2. 有两个特殊点：源点 s，汇点 t，要求 s\neq t。
• 流（一个边集函数）：
  1. 对于流满足 0\leq \text{f}(u,v)\leq \text{c}(u,v)。
  2. 除了 s 和 t，一个点出入的总流量应为 0，即 \text{F}(u)=\sum_p \text{f}(p,u)-\sum_p \text{f}(u,p)=0（这个表达式其实也是净流量）。原因很好想，就是一进一出。
  3. 对于一个流 \text{f}，它的净流量 |f| 为 \text{F}(s) 或 -\text{F}(t)。
  4. 我们把图 G 分为 S，T 两部分，要是一个流的 s\in S 且 t\in T，那么 {S,T} 是 G 的 s-t 割。这个东西的容量为 ||S,T||=\sum_{u\in S}\sum_{v\in T} \text{c}(u,v)。

2026/01/23：我忘记写残量网络是什么了，下面是它的定义：流完水后还有流量的边所组成的图叫做残量网络。

最大流

找一个流 \text{f} 使得图总流量最大。怎么说呢，分析下样例吧。

在 4 注无限多的水，只会在 3 流出 50。 我们就要算出这个最大的答案。