====== 网络流简介 ======

===== 网络 =====

首先，请分清楚 **网络** （或者流网络，Flow Network）与 **网络流** （Flow）的概念。

网络是指一个有向图 $G=(V,E)$。

每条边 $(u,v)\in E$ 都有一个权值 $c(u,v)$，称之为容量（Capacity），当 $(u,v)\notin E$ 时有 $c(u,v)=0$。

其中有两个特殊的点：源点（Source）$s\in V$ 和汇点（Sink）$t\in V,(s\ne t)$。

===== 流 =====

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

  - 容量限制：对于每条边，流经该边的流量不得超过该边的容量，即，$f(u,v)\le c(u,v)$。
  - 斜对称性：每条边的流量与其相反边的流量之和为 0，即 $f(u,v)=-f(v,u)$。
  - 流守恒性：从源点流出的流量等于汇点流入的流量，即 $\forall x\in V-\{s,t\},\sum_{(u,v)\in E}f(u,x)=\sum_{(x,v)\in E}f(s,v)$。

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

一般而言也可以把网络流理解为整个图的流量。而这个流量必满足上述三个性质。

//注//：流函数的完整定义为： $$
f(u,v)=\left\{\begin{aligned} &f(u,v),&(u,v)\in E\\
&-f(v,u),&(v,u)\in E\\
&0,&(u,v)\notin E,(v,u)\notin E \end{aligned}\right.
$$

===== 网络流的常见问题 =====

网络流问题中常见的有以下三种：最大流，最小割，费用流。

==== 最大流 ====

我们有一张图，要求从源点流向汇点的最大流量（可以有很多条路到达汇点），就是我们的最大流问题。

==== 最小费用最大流 ====

最小费用最大流问题是这样的：每条边都有一个费用，代表单位流量流过这条边的开销。我们要在求出最大流的同时，要求花费的费用最小。

==== 最小割 ====

割其实就是删边的意思，当然最小割就是割掉 $X$ 条边来让 $S$ 跟 $T$ 不互通。我们要求 $X$ 条边加起来的流量总和最小。这就是最小割问题。

===== 网络流 24 题 =====

[[https://loj.ac/problems/tag/30|网络流 24 题]]

===== 参考链接 =====

[[https://oi-wiki.org/graph/flow/|OI Wiki]]