网络流学习笔记

基础知识

定义

1. 网络 \(G = (V,E)\) 为有向图，边上有一权值 \(c(x,y)\) 为边的容量，有 \(\forall (x,y) \notin E,c(x,y) = 0\)。
2. 设定两个特殊的节点 \(S\) 源点 和 \(T\) 汇点，记 \(f(x,y)\) 为定义在二元组 \((x \in V,y \in V)\) 的函数，命名为流函数，则有以下三条性质：
3. 容量限制：\(f(x,y) \leq c(x,y)\)。
4. 斜对称：\(f(x,y) = -f(y,x)\)。
5. 流量守恒：\(\forall x \neq S,x \neq T,\sum_{(u,x) \in E} f(u,x) = \sum_{(x,v) \in E} f(x,v)\)。
6. 网络的流量为 \(\sum_{(S,v) \in E} f(S,v)\)。
7. 任意一条边的剩余流量定义为 \(r(x,y) = c(x,y) - f(x,y)\)。
8. 增广路：若 \(\exists w_{S \rightarrow T},\forall (u,v) \in w, r(u,v) > 0\)，则称 \(w\) 为一条增广路。
9. 残量网络：\(G' = (V' = V,E' = \lbrace (u,v) \in E | r(u,v) > 0 \rbrace)\)。

最大流

1. \(\text{Edmonds-Karp 动能算法}\)

   1. 算法流程：

      1. 使用 \(\text{BFS}\) 找到一条增广路

2. \(\text{Dinic}\)