Flow

网络流概述

来源
图论重要部分

网络

网络（Flow Network）不同于网络流（Flow）。
网络：一个有向图$G=(V,E)$,每条边$(u,v)$都有一个权值c，称为容量（capacity），若边不在E中，容量即为0.
有两个特殊点：源点（Source）和汇点（Sink）

流

设$f(u,v)$定义在二元组$(u\in V,v\in V)$上的实函数且：

• 容量限制：对每条边，流量不超过容量，即$f(u,v)\leq c(u,v)$
• 斜对称性：每条边的流量与其反向边的流量之和为0，即$f(u,v)=-f(v,u)$
• 流守恒性：从源点流出的流量等于汇点流入的流量。

则$f$为网络$G$的流函数，f称为流量，$c(u,v)-f(u,v)$称为剩余容量。
整个网络的流量为$\sum_{(s,v)\in E}f(s,v)$, 即从源点出发的所有流量之和。

常见网络流问题

最大流

有一张图，求从源点向汇点的最大流量。

费用流

每个边有费用，代表单位流量流过的cost，求最大流所有方案中最小费用的。

最小割

删掉X个边，让S和T不再连通，要求这X边的流量最小