说在前面
似乎鸽了不久,于是整一些最近复习写的题来水一篇写一篇。
预备知识
流网络(Flow Network)
流网络指的是一个有向图(G = (V,E)),同时:
- 对于每条边((u,v) in E),有容量(Capacity)(c(u,v)),流量(Flow)(f(u,v))。
注:为方便起见,对于((u,v) ot in E),定义(f(u,v) = c(u,v) = 0)。
其中,有两个点为源点(S)和汇点(T),(S)满足入度为0,(T)满足出度为0。
流与其基本性质
- 容量限制:即在任何时刻,对于所有的(u,v in V,0 le f(u,v) le c(u,v))。
- 流量守恒:即对于所有(u in V - {S,T}),满足
[sum_{v in V} f(v,u) = sum_{v in V} f(u,v)
]
- 斜对称性:即对于所有满足(u,v in V),满足(f(u,v) = -f(v,u))。
残量网络
若原图为(G = (V,E)),则残量网络即为(G' = (V' = V,E' = {(u,v) in E,c(u,v) > f(u,v)}))
增广路
在残量网络中(S)到(T)的一条路径。
最大流问题
指源点流到汇点的最大流量。
目前OI圈比较流行Dinic做法,时间复杂度为(mathcal{O}(n^2m)),学术界也有一些神仙做法能做到
(mathcal{O}(nm)),我当然是不会的。
Dinic用到了对图分层的方法,每次对残量网络bfs分层,然后再找增广路进行增广,同时对于每条边((u,v) in E),建一条反向边((v,u))进行反悔。
最小割问题
割的定义:对于一个流网络(G),删掉一些边使(S)和(T)不连通,割的容量指的是删掉的边的容量的总和。
最小割即为求最小割的容量。
有一个东西叫最大流最小割定理,看过【被迫营业10】的可能看到过。不证明了,也就是说最小割=最大流。
最小费用最大流问题
对于每条边((u,v) in E),除了有容量和流量。还有费用(w(u,v)),表示从这条边经过一个单位的流量需要花费(w(u,v))。
做法非常简单,只需要将分层的bfs换成spfa。
题目
飞行员配对方案问题 | 最小路径覆盖问题 | 最长不下降子序列问题 | 方格取数问题 | [SCOI2007]蜥蜴 |
---|---|---|---|---|
二分图最大匹配 | 拆点进行最大匹配 | dp,拆点进行容量限制跑最大流 | 总个数-最小割 | 总个数-最小割 |