学习笔记目录
有任何问题，欢迎私信/评论。
码字不易，求点赞啦~

网络流的基本概念

网络

网络指的是一张有向图。图中每一条边都有一个权值 $c(u,v)$ ，叫做边的容量。

图中还有两个特殊的点：源点 $s$ 与汇点 $t$。

流量

定义 $f(u,v)$ 是一条边 $(u,v)$ 的流量，那么 $f(u,v)$ 满足如下性质：

• 一条边的流量不得大于它的容量，$f(u,v)\leq c(u,v)$。
• 每条边的流量与其相反边的流量之和为 $0$，$f(u,v)+f(v,u)=0$。
• 从源点流出的流量等于汇点流入的流量。$\sum_{(u,x)\in E}f(u,x)=\sum_{(x,v)\in E}f(x,v)$。

可以把流量理解为城市排水系统中的水流。

割

在网络中选出一些边，使得这些边去掉后网络分割成了两个不连通子图，且源点 $s$ 和汇点 $t$ 分别属于这两个子图，那么选出的这些边构成的边集就是网络的一个割。

显然，一个网络的割不止一个。

在割中，所有从 $s$ 所在连通块指向 $t$ 所在连通块的边，叫做 正向边，所有从 $t$ 所在连通块指向 $s$ 所在连通块的边，叫做 反向边。

割的容量定义为割中所有正向边的流量之和。

关于割，有一个非常形象的比喻：恐怖分子想要切断自来水厂和你家之间的某些水管，让你家用不了水。定义切断一根水管的代价为这根水管得粗细（毕竟细一点的水管好切嘛）。割的容量就是恐怖分子所花费的代价。

增广路

增广路，简单来说就是从源点流向汇点的一条路径，且满足这条路径上所有的弧的残量均不为 $0$。