在 NOIP 前夕被要求写网络流感觉慌慌的，而且我自己也不怎么会这东西，参考这之前去日照的课件说吧。。
网络流本质是线性规划，用于一类最优解问题求解，是一种类比水流解决问题的方法。
主要以题目为主。
定义
有向图 $(V, E)$, 存在源点 $S \in V$ 和汇点 $T \in V,S \neq T$, 每条边有一个容量 $c$.
容量限制
每条边的流量 $f$ 是变量, 需要满足 $0 \leq f \leq c$.
流量平衡
对于每个非源汇点, 流入流量总和等于流出流量总和.
流量
$S$ 的流出流量与 $T$ 的流入流量相等, 称为网络的流量
最大流
在保证流量平衡的基础上求从源点流入汇点的最大流量为求解最大流问题。具体如何求解我只知道 Dinic，至于预留推进算法我也不怎么会。
最小费用最大流
给每条边额外增加一个单位流量费用，即流过一单位流量所需要的代价，在保证最大流的基础上使得总费用最小的问题即为最小费用最大流问题，于此对应的还用最大费用最大流，最小(大)费用可行流等……
最小割问题
简单来说即为求让使得源点和汇点不连通所需要删掉的边和流量和最小值的问题为最小割问题。
有一个定理，叫最小割最大流定理，即一个图的最小割即为此图的最大流，具体如何也不细说了，还是比较显然的。
所以直接跑最大流即可。
还有些事，先把概念整理出来，改天说题