网络流概述
定义
网络
-
网络
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 中的网络流,大概可以这么刻画:
-
通过各种方式,将复杂的实际问题转化成某种网络流模型,然后利用网络流算法来求解。
-
更具体地,网络流基本上都是“水流”模型的体现。最小割除外,它是“矛盾”。
-
更多的,还得等我多做做题,深入理解了再说。
-
另外值得指出的是,网络流本身的复杂度很差:一定程度上,它和矩阵一样维护了很多无用信息,故而建出网络后,拆网络流算法转而手动求解,也是一个常常发生的事情。