网络流概览
网络流是一种类比水流解决问题的办法。
一，相关概念
网络：指一张有向图 \(G=(V,E)\)；
弧：即网络中的有向边。
容量：网络中每条边的权值，即 \((u,v)\in E\) 的权值 \(c(u,v)\)。规定当 \((u,v)\notin E\) 时，\(c(u,v)=0\)，也就是说 \(u\) 无法向 \(v\) 出流。
流量：在网络中每条边都有一个流量，用 \(f(u,v)\) 表示，可以是负值。下文会详细介绍其性质。
残留容量：也称剩余容量，每条边除流量以外的容量，即残余容量=容量-流量。
源点：网络流的出发点 \(s\)，\(s\) 向外释放流量，\(s\in V\)。
汇点：网络流的结束点 \(t\)，\(t\) 接受流量，\(t\in V\)。
源点只释放流量，汇点只接受流量，其余点可以接受流量，但必须释放等量的流量。于是我们可以具象地理解一下网络流：网络即自来水系统，容量就是水管的最大水流量，源点是一个可无限出水的自来水厂，汇点是一个可无限接受水流的小区，其他结点起中转作用。可以想到一条自来水路线中最大的水流就等于水流量最小管道的水流量，若路线水流比该管道的水流量大，该管道无法接受。
容量网络：拥有源点汇点，且每条边都给出容量的网络。
流量网络：拥有源点汇点，且每条边都给出流量的网络。
残量网络：拥有源点汇点，且每条边都有残余容量的网络，残量网络=容量网络-流量网络。
二，流及其性质
对于一个流 \(f(u,v)\)，其满足如下性质：
容量限制：每条边的流量 \(f(u,v)\) 不得超过其容量 \(c(u,v)\)。
斜对称性：每条边的流量与其反向边的流量互为相反数。即 \(f(u,v)=-f(v,u)\)。
流守恒性：从源点出发的流量等于汇点流入的流量，其余点的出发流量等于其自身的流入流量。即 \(\forall x\in V-\) \(\{s,t\},\) \(\sum_{(u,x)\in E}f(u,x)=\) \(\sum_{(x,v)\in E}f(x,v)\)。
在此给出第二条性质的解释
如果我们认为由 \(u\) 流向 \(v\) 为正向的，那么由 \(v\) 流向 \(u\) 便是反向，正向中由 \(u\) 流向 \(v\) 的流量为 \(f(u,v)\)，那么我们可以认为这相当于其向反向流了 \(-f(u,v)\) 的流量，即 \(f(v,u)=-f(u,v)\)。
称 \(f\) 为网络 \(G\) 的流函数，整个网络的流量为 \(\sum_{(s,v)\in E}f(s,v)\)，即从源点出发的所有流量之和。
现在我们可以给出流函数的形式化定义:
$ f(u,v)=$ \({ \begin{cases}f(u,v),(u,v)\in E\\ -f(v,u),(v,u)\in E\\ 0,(u,v)\notin E,(v,u)\notin E\end{cases} }\)
三，网络流相关问题
在前文引言部分提到了网络流是一种类比水流解决问题的方法，以下为一些网络流的常见问题：
1. 最大流
给出一个网络，求源点流向汇点的最大流量。其求法与最短路的求法有些许相似之处，都会用到增广路的思想，详情请见最大流或最大流重制版。
2. 最小费用最大流
在最大流问题的基础上给每条边增加一个费用，在求最大流的同时使得花费最小，详情请见最小割。
3. 最小割
割，即删。最小割问题要求在网络中删除一些边使得 \(s\) 与 \(t\) 不互通，并且删去的边流量之和最小，详情请见费用流（目前还未完善）
4. 上下界网络流
每条边给定了流量上界与下界，根据题目要求问题也有所不同。（新建文件夹中……）
在网络流学习中可能会遇到许多抽象的概念或性质或思想，但可以勤思考，运用类比思想具象化，笔者也会尽量给出相关理解或证明。