网络流
网络:一类有向图 \(G=(V,E)\),\(E\) 中的每条边 \((u, v)\) 都有一个被称为容量的权值,记作 \(w(u, v)\);当 \((u,v)\notin E\) 时,可以假定 \(w(u,v)=0\)。
源点 \(s\) 和汇点 \(t\):网络中两个特殊的点。
流:每条边有一个额外的权值 \(f(u,v)\),称为流。流需要满足一些限制:
- 容量限制:对于每条边,流经该边的流量不得超过该边的容量,即 \(0\le f(u,v) \leq w(u,v)\);
- 流守恒:除 \(s,t\) 两点外,任意结点 \(u\) 的净流量为 \(0\)。
流的流量:\(s\) 的净流量(或 \(t\) 的净流量的相反数)称为流的流量。
\(s\)-\(t\) 割:若两个集合 \(S,T\) 满足 \(S\cup T=V\),\(S\cap T=\varnothing\),则称 \(\{S,T\}\) 为网络 \(G\) 的一个 \(s\)-\(t\) 割。
割的容量:\(\sum_{u\in S}\sum_{v\in T}{w(u,v)}\) 称为割 \(\{S,T\}\) 的容量。
最大流 / 最小割
我们主要使用增广路算法求得最大流 / 最小割。不同求最大流的算法的主要差异在于求增广路的算法。
定义残量网络 \(G'=(V,E')\),其上的边权(容量) \(g(u,v)=w(u,v)-f(u,v)\)。注意:反边在残量网络上也有对应的边,其容量为原边的流量。建出反边是为了方便退流,这本质上是一种反悔贪心,可以避免先前的错误决策导致整体变劣。
定义路径的容量为其上所有边的容量的最小值。我们只考虑容量不为 \(0\) 的路径。(否则没有意义)
残量网络中一条(容量不为 \(0\) 的)从 \(s\) 指向 \(t\) 的路径被称为增广路。
如果存在容量为 \(k\) 的增广路,则我们可以给增广路上的所有边都增加 \(k\) 的容量,使总流量增大 \(k\),而不影响流的合法性。因此,最大流的残量网络中一定不包含增广路。
最大流最小割定理
对于任意网络图 \(G=(V,E)\),其最大流 \(|f|\) 和最小割 \(||S,T||\) 大小相等。
该定理能够说明增广路算法求解最大流的正确性。
证明
引理
对于网络 \(G=(V,E)\) 和其上任意一个流 \(f\) 和割 \(\{S,T\}\),有 \(|f|\le||S,T||\)。
证明
第一个不等号在所有 \(T\rightarrow S\) 的边均空流时取等;第二个不等号在所有 \(S\rightarrow T\) 的边均空流时取等。
我们现在给出构造,证明存在一个流 \(f\) 和割 \(\{S,T\}\),使得 \(|f|=||\{S,T\}||\),显然此时 \(f\) 是最大流,\(||\{S,T\}||\) 是最小割。
考虑对原图不断增广,直到不存在增广路。此时在残量网络 \(G'\) 中,我们将源点 \(s\) 能够(通过容量不为 \(0\) 的边)到达的点组成的点集记为 \(S\),记 \(T=V/S\)。显然,所有 \(S\rightarrow T\) 的边均满流,所有 \(T\rightarrow S\) 的边均空流;否则从 \(s\) 点出发,可以沿着一条容量不为 \(0\) 的边走到 \(T\) 中的某个点。
这正是引理 中的取等条件。这说明流 \(f\) 和割 \(\{S,T\}\) 的容量相等。因此增广算法得到的一定是最大流,也即最小割。
Dinic 算法
Dinic 算法通过 bfs
得到每个点到源点 \(s\) 的距离 \(d(u)\),然后限制 dfs
只走最短的增广路。其时间复杂度不超过 \(O(n^2m)\)。
当所有边的边权均为 \(1\) 时,可以证明 Dinic 时间复杂度不超过 \(O\big(\min(m^{3/2},mn^{2/3})\big)\)。在所有边权等于 \(1\) 的情况下,如果除源汇点外每个结点 \(u\) 都满足 \(\min(deg_{in},deg_{out})=1\),则 Dinic 的时间复杂度为 \(O(mn^{1/2})\)。
Dinic 在绝大多数情况下跑的飞快,可以通过一些较大的数据。
网络流建模
许多非图论问题都可以通过建模转换成网络上的最大流 / 最小割问题。其建模方式因题而异,需要具体分析。
注意短路
建图时通常会使用到 \(+\infty\) 容量的边。如果 \(s\rightarrow t\) 之间存在容量为 \(+\infty\) 的路径,则会导致短路,使得最大流结果无效。因此需要特别注意输入数据是否会使建出的图短路。
技巧
我们希望构造出一个网络 \(G\),使得每种合法方案都一一对应 \(G\) 的一个 \(s\)-\(t\) 割,并且方案的代价等于割的容量。
这样,我们只需要求出 \(G\) 的最小割就是原问题的最优解。
P2774 方格取数问题
题意
有一个 \(n\) 行 \(m\) 列的方格图,每个方格中都有一个正整数。现要从方格中取数,使任意两个数所在方格没有公共边,且取出的数的总和最大,请求出最大的和。
\(n,m\le 100,\ a_i\le 10^5\)
网格图可以通过黑白染色转换成二分图,因此原问题可以规约到二分图最大权独立集。
我们从最小割的角度考虑,割掉 \(s\to u\) 或 \(u\to t\) 的一条边表示不选择点 \(u\);在互斥的节点之间连接一条容量为 \(+\infty\) 的边,表示两边的节点不能同时选。
显然,最大权独立集的大小等于总和减去最小割。写 Dinic 即可,跑的飞快。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 |
|
P4313 文理分科
题意
给定一个带权网格图,你需要将网格图上的每个格子染成黑白两种颜色。将点 \((i,j)\) 染成黑色会产生 \(a_{i,j}\) 的价值,染成白色产生 \(b_{i,j}\) 的价值。若一个点 \((i,j)\) 和相邻的点都为黑色,则额外产生 \(sa_{i,j}\) 价值;若都为白色,则额外产生 \(sb_{i,j}\) 的价值。
技巧
若题目表述为:“若满足一些条件,则产生额外的代价或价值”,可以考虑使用网络流最小割求解。