20220104-EK求最大流

发表于 阅读次数： 本文字数： 3.3k 阅读时长 ≈ 3 分钟

EK求最大流

1. 最大流知识点梳理

  • 基本概念
    • 流网络，不考虑反向边
    • 可行流，不考虑反向边
      • 两个条件：容量限制、流量守恒
      • 可行流的流量=从源点流出的流量-流入源点的流量
      • 最大流是指最大可行流
    • 残留网络，考虑反向边，残留网络的可行流$f^{‘}$ + 原图的可行流$f$ = 原图的另一个可行流
      • |f' + f| = |f'| + |f|
      • |f'| 可能是负数
    • 增广路径
    • 割
      • 割的定义
      • 割的容量，不考虑反向边，最小割是指容量最小的割
      • 割的流量，考虑反向边，f(S, T) <= c(S, T)
      • 对于任意可行流$f$，任意割[S, T]，有|f| = f(S, T) <= c(S, T)
      • 最大流最小割定理
        • 可行流$f$是最大流；
        • 可行流$f$的残留网络中不存在增广路；
        • 存在某个割[S, T]，有|f| = c(S, T)；
    • 算法【网络流的时间复杂度just a joke】
      • EK算法 $O(nm^2)$
      • Dinic算法 $O(n^2m)$
    • 应用
      • 二分图：二分图匹配、二分图多重匹配
      • 上下界网络流：无源汇上下界可行流、有源汇上下界最大流、有源汇上下界最小流
      • 多元汇最大流

2. EK算法具体实现

思路：首先存下图，建立反向边，构建残余网络，在残余网络中不断寻找增广路径，维护残余网络，将其累加至答案中，知道找不到增广路径。具体代码如下：

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
#include<bits/stdc++.h>
using namespace std;

const int N = 1010, M = 20010, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;   // f[i]代表编号为i的边的capacity
int q[N], d[N], pre[N]; // 当前边的编号、走到这条边的路径中最小的权值（最大的可行流量）、当前边的前驱路径
bool st[N];             // 标记bfs过程中已经达到了的点，防止重复搜索


void add(int a, int b, int c){
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;   // 构建正向边
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++;   // 构建反向边
}

bool bfs(){
    int hh = 0, tt = 0;
    
    memset(st, false, sizeof st);
    
    q[0] = S, st[S] = true, d[S] = INF; // 添加编号为1的边，终点为S
    
    while(hh <= tt){
        int t = q[hh++];
        for(int i = h[t]; ~i; i = ne[i]){
            int ver = e[i];
            if(!st[ver] && f[i]){   // 如果当前边的终点还没有到达过，且当前这条边的权值大于0
                st[ver] = true;
                d[ver] = min(d[t], f[i]);
                pre[ver] = i;
                if(ver == T)    return true;
                q[++tt] = ver;
            }
        }
    }
    return false;
}

int EK(){
    int r = 0;
    while(bfs()){   // 若当前残留网络中还可以找到增广路径，则累加到r中，并修改这条路径中正向边和反向边的权值
        r += d[T];
        for(int i = T; i != S; i = e[pre[i] ^ 1]){  // 回溯
            f[pre[i]] -= d[T];
            f[pre[i] ^ 1] += d[T];
        }
    }
    return r;
}

int main(){
    cin>>n>>m>>S>>T;
    memset(h, -1, sizeof h);
    while (m --){
        int a, b, c;    cin>>a>>b>>c;
        add(a, b, c);
    }
    
    cout<<EK()<<endl;
    return 0;
}

3. Dinic算法具体实现

概念：在稀疏图上和EK算法效果差不多，但是在稠密图上优势明显。

思路：EK算法在寻找增广路径时候是一条一条找的，显然比较低效。因此Dinic实现了多路增广；

  • 多路增广：在使用EK算法时，由于我们使用bfs找增广路，当每次贪心取得一条增广路并增广后，我们从汇点沿着增广路往前走，很可能会遇见一些点实际经过的流量小于该点所有入度的容量和，或者说在残量网络中，该点的入度和出度均大于0。我们可以利用该店后向弧的残量向该点前向弧增广。由于涉及回溯，bfs不适用；
  • 当前弧优化：对于增广操作，对于任意节点，我们每增广它的一条前向弧，意味着这条弧后所有的边都被我们多路增广过了，当我们再次处理该节点时，可以不用考虑这条弧。或者说，如果一条边已经被增广过，那么它就没有可能被增广第二次。那么我们下一次进行增广时，可以不走那些已经被增广过的边。
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
#include<bits/stdc++.h>

using namespace std;

const int N = 10010, M = 200010, INF = 1e8;

int n, m, S, T;
int h[N], e[M], f[M], ne[M], idx;
int q[N], d[N], cur[N];

void add(int a, int b, int c){
    e[idx] = b, f[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, f[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

bool bfs(){
    int hh = 0, tt = 0;
    memset(d, -1, sizeof d);
    q[0] = S, d[S] = 0, cur[S] = h[S];
    while(hh <= tt){
        int t = q[hh++];
        for(int i = h[t]; ~i; i = ne[i]){
            int ver = e[i]; // 当前弧优化
            if(d[ver] == -1 && f[i]){
                d[ver] = d[t] + 1;
                cur[ver] = h[ver];
                if(ver == T)    return true;
                q[++tt] = ver;
            }
        }
    }
    return false;
}

int find(int u, int limit){
    if(u == T)  return limit;
    int flow = 0;
    for(int i = cur[u]; ~i && flow < limit; i = ne[i]){
        cur[u] = i;
        int ver = e[i];
        if(d[ver] == d[u] + 1 && f[i]){
            int t = find(ver, min(f[i], limit - flow));
            if(!t)  d[ver] = -1;
            f[i] -= t;f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}

int dinic(){
    int r = 0, flow;
    while(bfs())    while(flow = find(S, INF))  r += flow;
    return r;
}

int main(){
    cin>>n>>m>>S>>T;
    memset(h, -1, sizeof h);
    while(m--){
        int a, b, c;    cin>>a>>b>>c;
        add(a, b, c);
    }
    
    cout<<dinic()<<endl;    
    return 0;
}