说明
在网络流相关问题中,在流网络(原网络)G=(V,E)G=(V, E) 中不考虑反向边
只有在任意流f\forall f 所对应的残量网络GfG_f 中,才考虑反向边

流网络

一个源点ss 和一个汇点tt
边集合EE 中包含一条边(u,v)(u, v),则不存在反向边(v,u)(v, u)
边的容量值为c(u,v)c(u, v),流量为f(u,v)f(u, v)

  • 容量限制

    u,vV,0f(u,v)c(u,v)\forall u, v \in V, \quad 0 \leqslant f(u, v) \leqslant c(u, v)

  • 流量守恒

    uV{s,t},vVf(v,u)=vVf(u,v)\forall u \in V - \{s, t\}, \quad \sum_{v \in V} f(v, u) = \sum_{v \in V} f(u, v)

    特别地,如果(u,v)E,f(u,v)=0(u, v) \notin E, f(u, v) = 0
  • f=vVf(s,v)vVf(v,s)|f| = \sum_{v \in V} f(s, v) - \sum_{v \in V} f(v, s)

Ford-Fulkerson 方法

  • 初始化流为f=0f = 0
  • while\textbf{while}在残量网络 Gf 中存在一条增广路径 p\text{在残量网络 } G_f \ \text{中存在一条增广路径} \ p
    沿着 p 增加流 f\text{沿着} \ p \ \text{增加流} \ f
  • return f\textbf{return} \ f

残量网络

augment-01

cf(u,v)={c(u,v)f(u,v)如果 (u,v)Ef(v,u)如果 (v,u)E0其他c_f(u, v) = \begin{cases} c(u, v) - f(u, v) && \text{如果} \ (u, v) \in E \\ f(v, u) && \text{如果} \ (v, u) \in E \\ 0 && \text{其他} \end{cases}

ff' 为残量网络中的一个流,定义fff' \uparrow f 为流ff'ff 的递增

(ff)(u,v)={f(u,v)+f(u,v)f(v,u)(u,v)E0其他(f \uparrow f')(u, v) = \begin{cases} f(u, v) + f'(u, v) - f'(v, u) && \text{若} (u, v) \in E \\ 0 && \text{其他} \end{cases}

  • 引理1
    G(V,E)G(V, E) 为流网络,设ffGG 中的一个流,GfG_f 为对应的残量网络
    ff'GfG_f 中的一个流,那么fff \uparrow f'GG 中的一个流
    并且ff=f+f|f \uparrow f'| = |f| + |f'|

    • 容量限制,f(v,u)cf(v,u)=f(u,v)f'(v, u) \leqslant c_f(v, u) = f(u, v)

      (ff)(u,v)=f(u,v)+f(u,v)f(v,u)f(v,u)f(u,v)f(u,v)+f(u,v)f(u,v)=f(u,v)0\begin{aligned} (f \uparrow f')(u, v) &= f(u, v) + f'(u, v) - f'(v, u) \xRightarrow{f'(v,u) \leqslant f(u,v)} \\ &\geqslant f(u, v) + f'(u, v) - f(u, v) = f'(u, v) \geqslant 0 \end{aligned}

      (ff)(u,v)=f(u,v)+f(u,v)f(v,u)f(v,u)0f(u,v)+f(u,v)f(u,v)+cf(u,v)=f(u,v)+c(u,v)f(u,v)=c(u,v)\begin{aligned} (f \uparrow f')(u, v) &= f(u, v) + f'(u, v) - f'(v, u) \xRightarrow{f'(v,u) \geqslant 0} \\ &\leqslant f(u, v) + f'(u, v) \leqslant f(u, v) + c_f(u, v) \\ &= f(u, v) + c(u, v) - f(u, v) = c(u, v) \end{aligned}

    • 流量守恒,对于所有节点uV{s,t}u \in V - \{s, t\}

      vV(ff)(u,v)=vV(f(u,v)+f(u,v)f(v,u))=vVf(u,v)+vVf(u,v)vVf(v,u)流量守恒=vVf(u,v)+vVf(v,u)vVf(u,v)=vV(f(v,u)+f(v,u)f(u,v))=vV(ff)(v,u)\begin{aligned} \sum_{v \in V}(f \uparrow f')(u, v) &= \sum_{v \in V} \left( f(u, v) + f'(u, v) - f'(v, u) \right) \\ &= \sum_{v \in V} f(u, v) + \sum_{v \in V} f'(u, v) - \sum_{v \in V} f'(v, u) \xRightarrow{\text{流量守恒}} \\ &= \sum_{v \in V} f(u, v) + \sum_{v \in V} f'(v, u) - \sum_{v \in V} f'(u, v) \\ &= \sum_{v \in V} \left( f(v, u) + f'(v, u) - f'(u, v) \right) \\ &= \sum_{v \in V} (f \uparrow f')(v, u) \end{aligned}

    • 流量计算
      V1={v:(s,v)E}V_1 = \{v : (s, v) \in E\} 表示从源点ss 流出的流量,流量能到达的点的集合
      V2={v:(v,s)E}V_2 = \{v : (v, s) \in E\} 表示流回源点ss 的流量,这些流量经过的点集

      ff=vV1(ff)(s,v)vV2(ff)(v,s)|f \uparrow f'| = \sum_{v \in V_1} (f \uparrow f')(s, v) - \sum_{v \in V_2} (f \uparrow f')(v, s)

      ff=vV1(f(s,v)+f(s,v)f(v,s))vV2(f(v,s)+f(v,s)f(s,v))=vV1f(s,v)+vV1f(s,v)vV1f(v,s)vV2f(v,s)vV2f(v,s)+vV2f(s,v)=vV1f(s,v)vV2f(v,s)+(vV1f(s,v)+vV2f(s,v))(vV1f(v,s)+vV2f(v,s))=(vV1f(s,v)vV2f(v,s))+(vV1V2f(s,v)vV1V2f(v,s))\begin{aligned} |f \uparrow f'| &= \sum_{v \in V_1} (f(s, v) + f'(s, v) - f'(v,s)) - \sum_{v\in V_2}(f(v,s) + f'(v,s) - f'(s, v)) \\ &= \sum_{v \in V_1}f(s, v) + \sum_{v \in V_1}f'(s, v) - \sum_{v \in V_1}f'(v, s) \\ &\quad - \sum_{v \in V_2}f(v, s) - \sum_{v \in V_2}f'(v,s) + \sum_{v \in V_2} f'(s, v) \\ &= \sum_{v \in V_1} f(s, v) - \sum_{v \in V_2}f(v,s) \\ &\quad + \left(\sum_{v \in V_1}f'(s, v) + \sum_{v \in V_2}f'(s, v) \right) - \left(\sum_{v \in V_1}f'(v, s) + \sum_{v \in V_2}f'(v,s) \right) \\ &= \left( \sum_{v \in V_1}f(s, v) - \sum_{v \in V_2}f(v,s) \right) + \left( \sum_{v \in V_1 \cup V_2} f'(s, v) - \sum_{v \in V_1 \cup V_2} f'(v,s) \right) \end{aligned}

      ff=f+f|f \uparrow f'| = |f| + |f'|

增广路径

augment-02
沿着增广路径走,注意GfG_f反向边流量增加
一条增广路径pp 能够给GG 每条边增加的流量最大值为路径pp残存容量

cf(p)=min{cf(u,v):(u,v) 属于路径 p}c_f(p) = \min \{c_f(u, v) : (u, v)\ \text{属于路径} \ p \}

  • 引理
    G=(V,E)G=(V, E) 为一个流网络,设ffGG 中的一个流,设pp 为残量网络GfG_f 中的一条增广路径

    fp(u,v)={cf(p)若 (u,v) 在 p0其他f_p(u, v) = \begin{cases} c_f(p) && \text{若} \ (u, v) \ \text{在} \ p \text{上} \\ 0 && \text{其他} \end{cases}

    fpf_p 是残量网络GfG_f 中的一个流,fp=cf(p)>0|f_p| = c_f(p) > 0

流网络的切割

一个流是最大流当且仅当残量网络中不包括任何增广路径
为了证明这个算法的正确性,先引入流网络切割的概念
augment-03

切割(S,T)(S, T) 将流网络划分成了SST=VST = V-S 两个集合
其中满足sSs \in S,tTt \in T
净流量

f(S,T)=uSvTf(u,v)uSvTf(v,u)f(S, T) = \sum_{u \in S} \sum_{v \in T} f(u, v) - \sum_{u \in S} \sum_{v \in T}f(v, u)

割的容量

c(S,T)=uSvTc(u,v)c(S, T) = \sum_{u \in S} \sum_{v \in T} c(u, v)

引理
ff 为流网络GG 的一个流,(S,T)(S, T) 为流网络的任意切割,则横跨任意切割 (S,T)\forall \ (S, T) 的净流量总相同
f(S,T)=ff(S, T) = |f|

  • 根据流量守恒
     uV{s,t}\forall \ u \in V- \{s, t\}

    vVf(u,v)vVf(v,u)=0\sum_{v \in V} f(u, v) - \sum_{v \in V} f(v, u) = 0

    uS{s}u \in S - \{s\} 进行求和

    uS{s}(vVf(u,v)vVf(v,u))=0\sum_{u \in S - \{s\}}\left( \sum_{v \in V}f(u, v) - \sum_{v \in V}f(v, u) \right) = 0

  • f|f| 的定义

    f=vVf(s,v)vVf(v,s)+uS{s}(vVf(u,v)vVf(v,u))|f| = \sum_{v \in V} f(s, v) - \sum_{v \in V} f(v, s) + \sum_{u \in S - \{s\}}\left( \sum_{v \in V}f(u, v) - \sum_{v \in V}f(v, u) \right)

    展开并且重新组合

    f=vVf(s,v)vVf(v,s)+uS{s}vVf(u,v)uS{s}vVf(v,u)=vV(f(s,v)+uS{s}f(u,v))vV(f(v,s)+uS{s}f(v,u))=vVuSf(u,v)vVuSf(v,u)\begin{aligned} |f| &= \sum_{v \in V}f(s, v) - \sum_{v \in V}f(v, s) + \sum_{u \in S - \{s\}}\sum_{v \in V}f(u, v) - \sum_{u \in S - \{s\}} \sum_{v \in V} f(v, u) \\ &= \sum_{v \in V} \left(f(s, v) + \sum_{u \in S - \{s\}}f(u, v) \right) - \sum_{v \in V} \left( f(v, s) + \sum_{u \in S - \{s\}} f(v, u) \right) \\ &= \sum_{v \in V}\sum_{u \in S} f(u, v) - \sum_{v \in V}\sum_{u \in S} f(v, u) \end{aligned}

    vVv \in V 拆点,拆成(vS)+(vT)(v \in S) + (v \in T)

    f=vSuSf(u,v)+vTuSf(u,v)vSuSf(v,u)vTuSf(v,u)=vTuSf(u,v)vTuSf(v,u)+(vSuSf(u,v)vSuSf(v,u))\begin{aligned} |f| &= \sum_{v \in S}\sum_{u \in S}f(u, v) + \sum_{v \in T} \sum_{u \in S}f(u, v) - \sum_{v \in S}\sum_{u \in S}f(v, u) - \sum_{v \in T} \sum_{u \in S}f(v, u) \\ &= \sum_{v \in T} \sum_{u \in S}f(u, v) - \sum_{v \in T} \sum_{u \in S}f(v, u) \\ &\quad + \left( \sum_{v \in S}\sum_{u \in S}f(u, v) - \sum_{v \in S}\sum_{u \in S}f(v, u) \right) \end{aligned}

    括号中的求和项实际上是一样的,可以消去。由此

    f=uSvTf(u,v)uSvTf(v,u)=f(S,T)|f| = \sum_{u \in S} \sum_{v \in T} f(u, v) - \sum_{u \in S} \sum_{v \in T}f(v, u) = f(S, T)

推论
流网络GG 中任意流ff 的值不能超过GG 的任意切割的容量

f=f(S,T)=uSvTf(u,v)uSvTf(v,u)uSvTf(u,v)uSvTc(u,v)=c(S,T)\begin{aligned} |f| &= f(S, T) = \sum_{u \in S} \sum_{v \in T}f(u, v) - \sum_{u \in S} \sum_{v \in T}f(v, u) \\ &\leqslant \sum_{u\in S} \sum_{v \in T} f(u, v) \leqslant \sum_{u \in S}\sum_{v \in T}c(u, v) = c(S, T) \end{aligned}

流网络中最大流的值实际上等于一个最小切割的容量

最大流最小切割定理

ff 为流网络G=(V,E)G=(V, E) 中的一个流,源点为ss,汇点为tt,以下条件等价

  1. ffGG 的一个最大流
  2. 残量网络GfG_f 中不包括任何增广路径
  3. f=c(S,T)|f|=c(S, T),其中(S,T)(S, T) 是流网络GG 的某个切割

证明如下

  • (1)(2)(1) \Rightarrow (2),这是显然的,因为如果有增广路径pp,那么可以让ff+fp|f| \leftarrow |f| + |f_p|
    f|f| 是最大流矛盾
  • (2)(3)(2) \Rightarrow (3)GfG_f 中没有任何增广路径,也就是说,残量网络GfG_f 不存在任何sts \to t 的路径
    不妨令S={vV:在 Gf 中存在一条从 s 到 v 的路径},T=VSS = \{v \in V: \text{在} \ G_f \ \text{中存在一条从} \ s \ \text{到} \ v \ \text{的路径}\}, \quad T = V-S
    显然sS,tSs \in S, \quad t \notin S,因此划分(S,T)(S, T) 作为流网络GG 的一个切割
    • uS,tTu \in S, \quad t \in T,也就是说(u,v)E(u, v) \in E,必然有(u,v)Ef(u, v) \notin E_f
      也就是说cf(u,v)=0c_f(u, v) = 0

      cf(u,v)={c(u,v)f(u,v)如果 (u,v)Ef(v,u)如果 (v,u)E0其他c_f(u, v) = \begin{cases} c(u, v) - f(u, v) && \text{如果} \ (u, v) \in E \\ f(v, u) && \text{如果} \ (v, u) \in E \\ 0 && \text{其他} \end{cases}

    • 也就是说,有f(u,v)=c(u,v)f(u, v) = c(u, v),并且f(v,u)=0f(v, u) = 0
    • 因此

      f(S,T)=uSvTf(u,v)vTuSf(v,u)=uSvTc(u,v)vTuS0=c(S,T)f(S, T) = \sum_{u \in S}\sum_{v \in T}f(u, v) - \sum_{v \in T}\sum_{u \in S}f(v, u) = \sum_{u\in S} \sum_{v \in T}c(u, v) - \sum_{v \in T} \sum_{u \in S} 0 = c(S, T)

  • (3)(1)(3) \Rightarrow (1)
    很显然fc(S,T)|f| \leqslant c(S, T)f=c(S,T)|f| = c(S, T) 取最大值

Ford-Fulkerson 算法

for  edge(u,v)G.E\textbf{for} \ \forall \text{ edge}(u, v) \in G.E
(u,v).f=0\quad (u, v).f = 0
while 在残量网络 Gf 存在一条 st 的增广路径 p\textbf{while} \ \text{在残量网络} \ G_f \ \text{存在一条} \ s\to t \ \text{的增广路径} \ p
cf(p)=min{cf(u,v)(u,v)p}\quad c_f(p) = \min \{c_f(u, v) \quad (u, v) \in p\}
for  edge(u,v)p\quad \textbf{for} \ \forall \ \text{edge}(u, v) \in p
if (u,v)E:(u,v).f=(u,v).f+cf(p)\quad \quad \textbf{if} \ (u, v) \in E: \quad (u, v).f = (u, v).f + c_f(p)
else:(v,u).f=(v,u).fcf(p)\quad \quad \textbf{else}: \quad (v, u).f = (v, u).f - c_f(p)

算法分析

  • while\bold{while} 循环中,使用bfs\bold{bfs} 找增广路,时间复杂度为O(V+E)=O(E)O(V+E) = O(E)
    也就是说,每执行一次while\bold{while} 循环,所需要的时间复杂度为O(E)O(E)
  • 最坏情况每次cf(p)=1c_f(p) = 1,每次只增加11while\textbf{while} 循环最坏执行O(f)O(|f|)
    时间复杂度为O(Ef)O(E |f|)

Edmonds-Karp 算法

  • 使用bfs\bold{bfs} 找增广路,选择sts \to t 的最短路径作为增广路
  • 其中每条边的权重为单位距离,δf(u,v)\delta_f(u, v) 表示残量网络GfG_f
    sts \to t 的最短路径距离,其中每条边的权重为单位距离
  • 时间复杂度O(VE2)O(VE^2)

引理
Edmonds-Karp\text{Edmonds-Karp} 算法运行在流网络G=(V,E)G=(V,E) 上,对于所有的节点vV{s,t}v \in V - \{s, t\}
残量网络GfG_f 的最短路径δf(s,v)\delta_f(s, v) 随着流量的递增而单调增加

假设存在一个流量递增操作fff \to f',对于GfG_f 中的边(u,v)(u, v)
δf(s,u)δf(s,u)\delta_{f'} (s, u) \geqslant \delta_f (s, u),但
δf(s,v)<δf(s,v)\delta_{f'} (s, v) < \delta_f (s, v)
另外根据bfs\textbf{bfs} 过程,对于边Ef(u,v)E_{f'}(u, v) 我们有
δf(s,v)=δf(s,u)+1\delta_{f'}(s, v) = \delta_{f'}(s, u) + 1

  • 对于(u,v)Ef(u, v) \in E_{f'},那么一定有(u,v)Ef(u, v) \notin E_f,否则的话

    δf(s,v)δf(s,u)+1因为(u,v)是可行势δf(s,u)+1=δf(s,v)\begin{aligned} \delta_{f}(s, v) &\leqslant \delta_{f}(s, u) + 1 \quad \text{因为} (u, v) \text{是可行势} \\ &\leqslant \delta_{f'}(s, u) + 1 = \delta_{f'}(s, v) \end{aligned}

    这与归纳假设矛盾
  • (u,v)Ef,(u,v)Ef(u, v) \in E_f, \quad (u, v)\notin E_{f'},意味着递增操作增加了vuv \to u 的流量,即检查了Ef(v,u)E_f(v, u)
    因为Edmonds-Karp\text{Edmonds-Karp} 算法沿着最短路径增加流,所以GfG_f 中从sus \to u 最短路径最后检查的边是(v,u)(v, u)

    δf(s,v)=δf(s,u)1δf(s,u)1=δf(s,v)2\begin{aligned} \delta_{f}(s, v) &= \delta_{f}(s, u) - 1 \\ &\leqslant \delta_{f'}(s, u) - 1 = \delta_{f'}(s, v)-2 \end{aligned}

    这个与δf(s,v)<δf(s,v)\delta_{f'}(s, v) < \delta_{f}(s, v) 矛盾

定理
Edmonds-Karp\text{Edmonds-Karp} 算法执行的流量递增操作总次数为O(VE)O(VE)
在残量网络GfG_f 中,对于增广路径pp,如果cf(p)=cf(u,v)c_f(p) = c_f(u, v)(u,v)(u, v) 是增广路径的关键边
(在前面的图中,就是容量为44 的那条边)
对于E|E| 中的每条边而言,其成为关键边的次数最多为V/2|V|/2

  • 沿着增广路径增加流,关键边从残量网络GfG_f 中消失,它再次成为关键边
    只有当(u,v)(u, v) 网络流量减小,也就是(v,u)(v, u) 出现在增广路径上的时候,如下图
    augment-04
  • 此时有
    δf(s,v)=δf(s,u)+1\delta_{f}(s, v) = \delta_{f}(s, u) + 1
    δf(s,u)=δf(s,v)+1\delta_{f'}(s, u) = \delta_{f'}(s, v) + 1
    因为δf(s,v)δf(s,v)\delta_{f}(s, v) \leqslant \delta_{f'}(s, v),所以有
    δf(s,u)=δf(s,v)+1δf(s,v)+1=δf(s,u)+2\delta_{f'}(s, u) = \delta_{f'}(s, v) + 1 \geqslant \delta_{f}(s, v) + 1 = \delta_{f} (s, u) + 2
  • (u,v)(u, v) 第一次成为关键边到下一次再成为关键边
    (s,u)(s, u) 之间的距离至少增加了22 个单位,因为sus \to u 最短路径不包括s,ts, t
    所以二者之间的距离最多为V2|V|-2
    因此(u,v)(u, v) 最多可以再成为关键边O(V/2)O(|V|/2)
    关键边的总数为O(EV/2)O(|E| \cdot |V|/2)

算法实现

Acwing2171

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
const int maxn = 1000 + 10, maxm = 20000 + 10;
const int inf = 0x3f3f3f3f;
int head[maxn], ver[maxm], edges[maxm], ne[maxm], tot = 1, n, m, S, T;
int d[maxn], pre[maxn], vis[maxn];

void add(int a, int b, int c) {
ver[++tot] = b; edges[tot] = c; ne[tot] = head[a]; head[a] = tot;
}

bool bfs() {
memset(vis, 0, sizeof vis);
memset(d, 0, sizeof d);
memset(pre, 0, sizeof pre);
queue<int> q;

vis[S] = 1, d[S] = inf, q.push(S);
while (q.size()) {
int x = q.front(); q.pop();
for (int i = head[x]; i; i = ne[i]) {
int y = ver[i];
if (!vis[y] && edges[i] > 0) {
vis[y] = true;
d[y] = min(d[x], edges[i]);
pre[y] = i;
if (y == T) return true;
q.push(y);
}
}
}
return false;
}

void EK() {
int res = 0;
while (bfs()) {
res += d[T];
for (int i = T; i != S; i = ver[pre[i] ^ 1]) {
int id = pre[i];
edges[id] -= d[T], edges[id ^ 1] += d[T];
}
}
printf("%d\n", res);
}

int main() {
//freopen("input.txt", "r", stdin);
scanf("%d%d%d%d", &n, &m, &S, &T);
for (int i = 0; i < m; i++) {
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
add(a, b, c);
add(b, a, 0);
}

// Edmonds karp
EK();
}