最大流

1. 简介

最大流算法主要分为两大类，一类为增广路算法，一类为预流推进算法。最大流算法解决的是在有向网路图 G=(V,E) G = (V,E) 中计算从源点 ss 到汇点 tt 的最大流量问题，以及最小割容量问题。

  • 最小割最大流定理
    s−ts-t 最大流的值等于 s−ts-t 的最小割容量。

2. 增广路算法

  • 剩余容量
    剩余容量 cf(u,v)=c(u,v)−f(u,v) c_f(u,v) = c(u,v) - f(u,v) 表示边 (u,v)(u,v) 的容量与流量之差。

  • 增广路
    对于一个网络图 G=(V,E) G = (V,E) ，从图 G 中找到一条从源节点 ss 到目标节点 tt 的路径，且路径上所有边的剩余容量都大于 0 ，则这条路径称为增广路 。

  • 残量网络
    对于网络图 GG，残量网络定义为网络 G 中所有节点和剩余容量大于 0 的边构成的子图，即

Gf=(Vf=V,Ef=(u,v)∈E,cf(u,v)>0)\begin{array}{c} G_f = (V_f = V, E_f = {(u,v) \in E, c_f(u,v) \gt 0}) \end{array}

2.1 EK 算法

  • BFS 寻找增广路，一次 BFS 一次增广
  • 每一条有向边都需要构造反向边，因为当前增广路可能不是最优的，后续增广可能需要修改流量流向。

EK 算法复杂度为 O(nm2)O(nm^2)（nn 为节点数，mm 为边数）。

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

#ifndef _EK_
#define _EK_
#define ll long long 
#define MAXN 505
#define MAXM 240005
#define INF 1e12

// EK 算法
struct EK {
    ll cnt_edge;    // 边数
    ll head[MAXN];  // 节点的第一条边的编号
    ll flag[MAXN];  // 节点标记数组
    // 链式前向星
    struct edge {
        ll to, next, flow; // 分别代表：边的终点、同起点的下一条边的编号、边的流量
        edge() {}
        edge(ll _to, ll _next, ll _flow): to(_to), next(_next), flow(_flow) {}
    }e[MAXM];       // 边数组 
    // 增广路径
    struct path {
        ll from, index; // 分别代表：边的起点，边的编号
    }p[MAXN];
    EK() {}
    // 初始化前向星结构
    void init(ll n) {
        cnt_edge = 0;
        memset(head, -1, sizeof(ll)*(n+1));
    }
    // 添加边（正反向两条边）
    void addEdge(ll u, ll v, ll w) {
        e[cnt_edge].to = v;
        e[cnt_edge].next = head[u];
        e[cnt_edge].flow = w;
        head[u] = cnt_edge++;
        e[cnt_edge].to = u;
        e[cnt_edge].next = head[v];
        e[cnt_edge].flow = 0;
        head[v] = cnt_edge++;
    }
    // BFS 寻找增广路
    bool bfs(ll s, ll t, ll n) {
        memset(flag, 0, sizeof(ll)*(n+1));
        memset(p, -1, sizeof(ll)*(n+1));
        queue <ll> bfsq;
        bfsq.push(s);
        while(!bfsq.empty()) {
            ll u = bfsq.front();
            bfsq.pop();
            for(ll i = head[u]; i != -1; i = e[i].next) {
                ll v = e[i].to, w = e[i].flow;
                if(!flag[v] && w) {
                    flag[v] = 1;
                    p[v].from = u;
                    p[v].index = i;
                    if(v == t) {
                        return true;
                    }
                    bfsq.push(v);
                }
            }
        }
        // 没有找到增广路
        return false;
    }
    // 求最大流
    ll maxFlow(ll s, ll t, ll n) {
        ll ans = 0;
        while(bfs(s,t,n)) {
            ll maxflow = INF;
            for(ll i = t; i != s; i = p[i].from) {
                maxflow = min(maxflow, e[p[i].index].flow);
            }
            for(ll i = t; i != s; i = p[i].from) {
                e[p[i].index].flow -= maxflow;
                e[p[i].index ^ 1].flow += maxflow;
            }
            ans += maxflow;
        }
        return ans;
    }
};
#endif

2.2 Dinic 算法

可以看出，EK 算法存在以下明显不足：

  • 一次 BFS 只增广一次，如果残量网络中还存在增广路则被浪费了。
  • 对于已经没有剩余容量的边，EK 算法仍然进行增广判断从而导致时间上的浪费。

层次深度

当前节点到源点的最短路径长度（边权值视为 1 ）。

Dinic 算法则巧妙解决了 EK 算法的不足之处：

  • 一次 BFS 后使用 DFS 进行多次增广。
  • DFS 多次增广过程中，对于已经没有容量的边，采用弧优化的方法巧妙避免重复增广判断。

Dinic 算法的复杂度为 O(n2m)O(n^2m)（nn 为节点数，mm 为边数）。在稀疏图上，Dinic 算法和 EK 算法相差不大，但在稠密图上（二分匹配之类的）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
#include <bits/stdc++.h>
using namespace std;

#ifndef _DINIC_
#define _DINIC_
#define ll long long 
#define MAXN 505
#define MAXM 250005
#define INF 1e12

// Dinic 算法
struct Dinic {
    ll cnt_edge;    // 边数
    ll head[MAXN];  // 节点的第一条边的编号
    ll shead[MAXN]; // shead 用来临时保存 head 的副本
    ll level[MAXN]; // 节点所在层次
    // 链式前向星
    struct edge {
        ll to, next, flow; // 分别代表：边的终点、同起点的下一条边的编号、边的流量
        edge() {}
        edge(ll _to, ll _next, ll _flow): to(_to), next(_next), flow(_flow) {}
    }e[MAXM];       // 边数组 
    Dinic() {}
    // 初始化前向星结构
    void init(ll n) {
        cnt_edge = 0;
        memset(head, -1, sizeof(ll)*(n+1));
    }
    // 添加边（正反向两条边）
    void addEdge(ll u, ll v, ll w) {
        e[cnt_edge].to = v;
        e[cnt_edge].next = head[u];
        e[cnt_edge].flow = w;
        head[u] = cnt_edge++;
        e[cnt_edge].to = u;
        e[cnt_edge].next = head[v];
        e[cnt_edge].flow = 0;
        head[v] = cnt_edge++;
    }
    // BFS 寻找增广路，构建层次网络
    bool bfs(ll s, ll t, ll n) {
        memset(level, 0, sizeof(ll)*(n+1));
        queue <ll> bfsq;
        bfsq.push(s);
        level[s] = 1;   // 0 用来表示没有 bfs 到，故源点深度从 1 开始
        while(!bfsq.empty()) {
            ll u = bfsq.front();
            bfsq.pop();
            for(ll i = head[u]; i != -1; i = e[i].next) {
                ll v = e[i].to, w = e[i].flow;
                if(!level[v] && w) {
                    level[v] = level[u] + 1;
                    bfsq.push(v);
                }
            }
        }
        if(level[t])    return true;
        return false;
    }
    // DFS 进行路径增广
    ll dfs(ll u, ll curflow, ll t) {
        if(u == t) {
            return curflow;
        }
        for(ll & i = shead[u]; i != -1; i = e[i].next) {
            ll v = e[i].to, w = e[i].flow;
            if(level[v] == level[u] + 1 && w) {
                ll maxflow = dfs(v, min(curflow, w), t);
                if(maxflow) {
                    e[i].flow -= maxflow;
                    e[i^1].flow += maxflow;
                    return maxflow;
                }
            }
        }
        return 0;
    }
    // 求最大流
    ll maxFlow(ll s, ll t, ll n) {
        ll ans = 0;
        while(bfs(s,t,n)) {
            ll maxflow = INF, curflow;
            memcpy(shead, head, sizeof(head));
            while((curflow = dfs(s, maxflow, t))) {
                ans += curflow;
            }
        }
        return ans;
    }
};
#endif

2.3 ISAP 算法

SAP 算法引入了断层的优化方法：

  • 距离
    当前节点到汇点的最短路径长度（边权值视为 1 ）。类似于 Dinic 算法中的层次深度的计算，不过是在反图上从汇点到源点进行 BFS 。

  • 断层
    gap[i]gap[i] 数组用来统计距离为 ii 的节点个数。如果增广到某一距离发现节点数为零，需要重新计算所有节点的距离并计算 gap ；如果重新计算后仍然无法增广，则说明源点和汇点之间出现了断层，此时算法结束。

SAP 算法复杂度为 O(n2m)O(n^2m)（nn 为节点数，mm 为边数）。

  • ISAP 算法即为 SAP 算法的优化版本，在 SAP 算法基础上加上了当前弧优化和分层优化（即 DFS 后不需要重跑 BFS 来进行分层）。

ISAP 算法复杂度为 O(n2m)O(n^2m)（nn 为节点数，mm 为边数）。

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
109
110
111
112
113
114
115
116
117
118
119
120
121
#include <bits/stdc++.h>
using namespace std;

#ifndef _ISAP_
#define _ISAP_
#define ll long long 
#define MAXN 1205
#define MAXM 240005
#define INF 1e12

// ISAP 算法
struct ISAP {
    ll cnt_edge;    // 边数
    ll head[MAXN];  // 节点的第一条边的编号
    ll shead[MAXN]; // shead 用来临时保存 head 的副本
    ll level[MAXN]; // 节点所在层次
    ll gap[MAXN+1];   // 层次节点数
    // 链式前向星
    struct edge {
        ll to, next, flow; // 分别代表：边的终点、同起点的下一条边的编号、边的流量
        edge() {}
        edge(ll _to, ll _next, ll _flow): to(_to), next(_next), flow(_flow) {}
    }e[MAXM];       // 边数组 
    ISAP() {}
    // 初始化前向星结构
    void init(ll n) {
        cnt_edge = 0;
        memset(head, -1, sizeof(ll)*(n+1));
    }
    // 添加边（正反向两条边）
    void addEdge(ll u, ll v, ll w) {
        e[cnt_edge].to = v;
        e[cnt_edge].next = head[u];
        e[cnt_edge].flow = w;
        head[u] = cnt_edge++;
        e[cnt_edge].to = u;
        e[cnt_edge].next = head[v];
        e[cnt_edge].flow = 0;
        head[v] = cnt_edge++;
    }
    // BFS 寻找增广路，构建层次网络
    bool bfs(ll s, ll t, ll n) {
        memset(level, 0, sizeof(ll)*(n+1));
        memset(gap, 0, sizeof(ll)*(n+2));   // 最大 level 可达 n+1（见下文）
        queue <ll> bfsq;
        level[t] = 1;   // 0 用来表示没有 bfs 到，故到汇点的距离从 1 开始
        gap[1] = 1;    
        bfsq.push(t); 
        while(!bfsq.empty()) {
            ll u = bfsq.front();
            bfsq.pop();
            for(ll i = head[u]; i != -1; i = e[i].next) {
                // 在反图中构建层次网络，故需反向判断路径容量
                ll v = e[i].to;
                if(!level[v] && e[i^1].flow) {
                    level[v] = level[u] + 1;
                    ++gap[level[v]];
                    bfsq.push(v);
                }
            }
        }
        // 判断 s 到 t 是否有增广路
        if(level[s])    return true;
        return false;
    }
    // 重贴标签（更新层次深度）
    void relabel(ll u, ll n) {
        level[u] = n + 1;
        for(ll i = head[u]; i != -1; i = e[i].next) {
            ll v = e[i].to, w = e[i].flow;
            if(level[v] < level[u] - 1 && w) {
                level[u] = level[v] + 1;
            }
        }
    }
    // DFS 进行路径增广
    ll dfs(ll u, ll curflow, ll s, ll t, ll n) {
        if(u == t) {
            return curflow;
        }
        for(ll & i = shead[u]; i != -1; i = e[i].next) {
            ll v = e[i].to, w = e[i].flow;
            if(level[v] == level[u] - 1 && w) {
                ll maxflow = dfs(v, min(curflow, w), s, t, n);
                if(maxflow) {
                    e[i].flow -= maxflow;
                    e[i^1].flow += maxflow;
                    return maxflow;
                }
            }
        }
        // 程序执行到此说明该点出去的所有点都已经流过了
        // 此时需要更改层次深度
        // 同样要更新对应点的 shead
        shead[u] = head[u];
        --gap[level[u]];
        if(gap[level[u]] == 0) {
            level[s] = n + 1;
        }
        // 提高当前层次深度（因为可能存在路径更长的增广）
        // 方案一：直接更新为出边的最小层次深度+1
        relabel(u, n);
        // 方案二：直接更新为原层次深度+1
        // ++level[u];
        ++gap[level[u]];
        return 0;
    }
    // 求最大流
    ll maxFlow(ll s, ll t, ll n) {
        ll ans = 0;
        if(bfs(s,t,n)) {
            ll maxflow = INF;
            memcpy(shead, head, sizeof(head));
            while(level[s] <= n) {
                ans += dfs(s, maxflow, s, t, n);
            }
        }
        return ans;
    }
};
#endif

3. 预流推进算法

预流推进算法的主要思想是允许水在非源汇点的节点中暂时存储，然后每个节点都尽可能将自身的超额流推送出去，并且保证在算法结束后所有非源汇点的超额流都为0，那这种方案就是合法的。

  • 超额流
    存储在非源汇点中的流称作这个点的超额流。

3.1 HLPP 算法

HLPP 算法的主要思想如下：

  • 对于非源汇点的层次深度，每次选择层次深度最大的节点进行推流；
  • 如果节点推流后还有余流，则对该节点重贴标签后抬高其高度，回到上一步骤；
  • 直到所有非汇源点的余流都等于零，程序结束。

GAP 优化

  • 当出现断层后，直接将断层以上深度的所有节点的层次深度设为 n+1n + 1，使得这些再也无法推流到汇点的节点的余流尽快推送回源点，从而减少重贴标签的操作。

HLPP 算法复杂度为 O(n2m)O(n^2 \sqrt{m})（nn 为节点数，mm 为边数）。

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <bits/stdc++.h>
using namespace std;

#ifndef _HLPP_
#define _HLPP_
#define ll long long 
#define MAXN 1205
#define MAXM 240005
#define INF 1e12

// HLPP 算法
struct HLPP {
    ll cnt_edge;    // 边数
    ll head[MAXN];  // 节点的第一条边的编号
    ll rflow[MAXN]; // 每个点对应的余流（所有节点的余流初始化为0）
    ll level[MAXN]; // 节点所在层次
    ll flag[MAXN];  // 标记是否已经在层次深度链表数组中
    ll gap[MAXN<<1];        // 层次节点数，重贴标签后层次深度可能达到 2n
    // 层次深度结构体
    struct depth {
        ll node;    // 节点编号
        ll level;   // 节点层次深度
        depth() {}
        depth(ll _node, ll _level): node(_node), level(_level) {}
        bool operator < (const depth d) const {
            return level < d.level;
        }
    };
    // 层次深度优先队列
    priority_queue <depth> pq;
    // 链式前向星
    struct edge {
        ll to, next, flow; // 分别代表：边的终点、同起点的下一条边的编号、边的流量
        edge() {}
        edge(ll _to, ll _next, ll _flow): to(_to), next(_next), flow(_flow) {}
    }e[MAXM];       // 边数组 
    HLPP() {}
    // 初始化前向星结构
    void init(ll n) {
        cnt_edge = 0;
        memset(head, -1, sizeof(ll)*(n+1));
    }
    // 添加边（正反向两条边）
    void addEdge(ll u, ll v, ll w) {
        e[cnt_edge].to = v;
        e[cnt_edge].next = head[u];
        e[cnt_edge].flow = w;
        head[u] = cnt_edge++;
        e[cnt_edge].to = u;
        e[cnt_edge].next = head[v];
        e[cnt_edge].flow = 0;
        head[v] = cnt_edge++;
    }
    // BFS 寻找增广路，构建层次网络（反向构建）
    bool bfs(ll s, ll t, ll n) {
        memset(level, 0, sizeof(ll)*(n+1));
        queue <ll> bfsq;
        level[t] = 1;   // 0 用来表示没有 bfs 到，故到汇点的距离从 1 开始
        bfsq.push(t); 
        while(!bfsq.empty()) {
            ll u = bfsq.front();
            bfsq.pop();
            for(ll i = head[u]; i != -1; i = e[i].next) {
                // 在反图中构建层次网络，故需反向判断路径容量
                ll v = e[i].to;
                if(!level[v] && e[i^1].flow) {
                    level[v] = level[u] + 1;
                    bfsq.push(v);
                }
            }
        }
        // 判断 s 到 t 是否有增广路
        if(level[s])    return true;
        return false;
    }
    // 预流推进
    void preflowPush(ll u, ll s, ll t) {
        for(ll i = head[u]; i != -1; i = e[i].next) {
            ll v = e[i].to, w = e[i].flow;
            if(level[v] == level[u] - 1 && w) {
                ll maxflow = min(rflow[u], e[i].flow);
                e[i].flow -= maxflow;
                e[i^1].flow += maxflow;
                rflow[u] -= maxflow;
                rflow[v] += maxflow;
                if(v != s && v != t && !flag[v]) {
                    pq.push(depth{v, level[v]});
                    flag[v] = 1;
                }
                if(rflow[u] == 0) {
                    // 全部流量推送完毕
                    break;
                }
            }
        }
    }
    // 重贴标签（更新层次深度）
    void relabel(ll u, ll n) {
        level[u] = 2*n;
        for(ll i = head[u]; i != -1; i = e[i].next) {
            ll v = e[i].to, w = e[i].flow;
            if(level[v] < level[u] - 1 && w) {
                level[u] = level[v] + 1;
            }
        }
    }
    // 求最大流
    ll maxFlow(ll s, ll t, ll n) {
        if(!bfs(s,t,n)) {
            return 0;
        }
        // 防止s的临近节点过早的推流回s节点
        level[s] = n + 1;
        // 初始化 gap 数组
        memset(gap, 0, sizeof(ll)*((n+1)<<1));
        for(ll i = 1; i <= n; ++i) {
            if(level[i]) {
                ++gap[level[i]];
            }
        }
        // 设定源点 s 的出边节点初始余流
        for(ll i = head[s]; i != -1; i = e[i].next) {
            ll v = e[i].to, w = e[i].flow;
            if(w) {
                e[i].flow -= w;
                e[i^1].flow += w;
                rflow[s] -= w;
                rflow[v] += w;
                if(v != s && v != t && !flag[v]) {
                    pq.push(depth{v, level[v]});
                    flag[v] = 1;
                }
            }
        }
        // 开始从最高高度节点预推流
        while(!pq.empty()) {
            ll u = pq.top().node;
            pq.pop();
            flag[u] = 0;
            preflowPush(u, s, t);
            if(rflow[u]) {
                // 如果当前节点还有余流
                --gap[level[u]];
                if(!gap[level[u]]) {
                    // 断层
                    for(ll v = 1; v <= n; ++v) {
                        if(v != s && v != t && level[v] > level[u] && level[v] < n + 1) {
                            level[v] = n + 1;
                        }
                    }
                }
                relabel(u, n); // 重贴标签，提升高度
                ++gap[level[u]];
                pq.push(depth{u, level[u]});
                flag[u] = 1;
            }
        }
        return rflow[t];
    }
};
#endif