网络流概述
定义
网络
-
网络
G=(V,E) 是一张特殊的有向图。其特殊就在于，\forall (u,v)\in E ，有一个容量c(u,v) ，c 是 capacity。 -
特别地，如果
(u,v)\notin E ，c(u,v)=0 。 -
（有源汇）网络中还有两个关键点：源点，记作
S ；汇点，记作T 。
流函数
-
流函数
f(u,v) 是定义在网络的节点二元组（可以认为就是边，毕竟网络中所有点之间都有边，只是可能c=0 ）上的实数函数。 -
其满足以下三个性质：
-
1.容量限制：
f(u,v)\leqslant c(u,v) ，即流量不能超过容量。 -
2.斜对称性：
f(u,v)=-f(u,v) ，即...即对冲性？ -
3.流量守恒：
\forall u\notin\{S,T\} ，\sum f(x,u)=\sum f(u,y) ，即流入量等于流出量。
-
流量
-
对于
(u,v) ，f(u,v) 称为其流量，c(u,v)-f(u,v) 称为其剩余容量或残量。特别地，f 表示整个网络的流量（当然，只在有源汇的前提下有意义）。 -
如无特别说明，下文中的
c(u,v) 都是边(u,v) 的残量，都是在残量网络上的讨论。 -
-
最大流：使网络流量最大的流函数（这里的流函数是相对于网络而言的），有时也记为
f 。 -
最小费用最大流：对每条边附加一个权重
w(u,v) 表示该边每单位流量的费用，则最小费用最大流是在网络流量最大的前提下，总费用最小的流函数。 -
割：指满足删去该边集后，网络不再连通的边集
E'\subseteq E ，记为c 。如果有源汇，那么该定义等价于一个边集E'\subseteq E ，使得原网络的子网络G'=(V,\complement_E E') 的流量为0 ，即S,T 不连通，记为c(S,T) 。 -
最小割：一般指容量最小的割，这里的容量指的是
\sum\limits_{e\in E'} c(e) 。这里的c 就是容量，不是残量。
概述
-
OI 中的网络流，大概可以这么刻画：
-
通过各种方式，将复杂的实际问题转化成某种网络流模型，然后利用网络流算法来求解。
-
更具体地，网络流基本上都是“水流”模型的体现。最小割除外，它是“矛盾”。
-
更多的，还得等我多做做题，深入理解了再说。
-
另外值得指出的是，网络流本身的复杂度很差：一定程度上，它和矩阵一样维护了很多无用信息，故而建出网络后，拆网络流算法转而手动求解，也是一个常常发生的事情。