网络流基础

网络流合集链接：网络流

网络 $G = (V, E)$ 实际上是一张有向图

对于图中每一条有向边 $(x, y) \in E$ 都有一个给定的容量 $c(x, y)$

特别的，若 $(x,y) \notin E$ , 则 $c(x, y) = 0$

图中还有两个指定的特殊结点，$S, T (S \ne T)$ ，分别称为源点和汇点。

对于网络有一个流函数 $f$。对于 $(x, y) \in E$，$f(x, y)$ 称为边的流量，$c(x, y) - f(x, y)$称为边的剩余流量

流函数满足以下性质：

• 容量限制：$f(x, y) \le c(x, y)$

• 斜对称：$f(x, y) = -f(y, x)$

• 流量守恒：$\forall x \ne S, x \ne T, \sum_{(u, x)\in E} f(u, x) = \sum_{(x, v) \in E} f(x, v)$ 说人话：流入=流出

能量守恒定律也告诉我们网络中除了源点和汇点以外，任何结点不储存流量，其流入量等于流出量。

网络流模型可以概括为：在不超过容量限制的前提下，“流”从源点源源不断产生，流经整个网络，最终全部归于汇点。

生动一点，也可以把网络流看作水网，每一个管道有其流量限制，水流从源点流入，在不超过流量限制下，经过一些管道从源点流出，便是网络流模型。

基础知识就这些了，其他知识请慢慢享用^_^