一、亿些小定义

网络：是一张图 \(G=(V,E)\)，每一条边 \((u,v)\) 都有容量限制 \(c(u,v)\)，其流量为 \(f(u,v)\)。

定义流量函数为 \(f:V\times V \to \mathbb{R}\)，是点集中二元组对实数的一个映射，\(f(u,v)\) 表示边 \((u,v)\) 的流量，\(f\) 函数满足以下三条性质：

• 容量限制：\(f(u,v) \leq c(u,v)\)，若 \(f(u,v)=c(u,v)\) 则称 \((u,v)\) 满流。

• 反对称性：\(f(u,v)=-f(v,u)\)，你可以认为如果从 \(s\) 到 \(t\) 有 \(100\) 的流量，那么从 \(t\) 到 \(s\) 就有 \(-100\) 的流量。

• 流守恒性：每个节点（除源点、汇点）流入多少流量就流出多少流量，即对于 \(u(u \neq s,u \neq t)\)，有：\(\displaystyle \sum_{(u',u) \in E}f(u',u)=\sum_{(u,v)\in E}f(u,v)\)。

流量：在有源汇网络中，根据流守恒性，有 \(\displaystyle \sum f(s,u)=\sum f(u,t)\)，那么这个值就称作流量。

残量网络：定义残量网络 \(G_f\) 为流量函数为 \(c'(u,v)=c(u,v)-f(u,v)\) 的网络。

增广路：定义