1. 简介
最大流算法主要分为两大类,一类为增广路算法,一类为预流推进算法。最大流算法解决的是在有向网路图 G=(V,E) 中计算从源点 s 到汇点 t 的最大流量问题,以及最小割容量问题。
- 最小割最大流定理
s−t 最大流的值等于 s−t 的最小割容量。
2. 增广路算法
-
剩余容量
剩余容量 cf(u,v)=c(u,v)−f(u,v) 表示边 (u,v) 的容量与流量之差。
-
增广路
对于一个网络图 G=(V,E),从图 G 中找到一条从源节点 s 到目标节点 t 的路径,且路径上所有边的剩余容量都大于 0 ,则这条路径称为增广路 。
-
残量网络
对于网络图 G,残量网络定义为网络 G 中所有节点和剩余容量大于 0 的边构成的子图,即
Gf=(Vf=V,Ef=(u,v)∈E,cf(u,v)>0)
2.1 EK 算法
- BFS 寻找增广路,一次 BFS 一次增广
- 每一条有向边都需要构造反向边,因为当前增广路可能不是最优的,后续增广可能需要修改流量流向。
EK 算法复杂度为 O(nm2)(n 为节点数,m 为边数)。
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
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++; } 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)(n 为节点数,m 为边数)。在稀疏图上,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
struct Dinic { ll cnt_edge; ll head[MAXN]; ll shead[MAXN]; 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++; } bool bfs(ll s, ll t, ll n) { memset(level, 0, sizeof(ll)*(n+1)); queue <ll> bfsq; bfsq.push(s); level[s] = 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; } 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 算法引入了断层的优化方法:
SAP 算法复杂度为 O(n2m)(n 为节点数,m 为边数)。
- ISAP 算法即为 SAP 算法的优化版本,在 SAP 算法基础上加上了当前弧优化和分层优化(即 DFS 后不需要重跑 BFS 来进行分层)。
ISAP 算法复杂度为 O(n2m)(n 为节点数,m 为边数)。
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
struct ISAP { ll cnt_edge; ll head[MAXN]; ll shead[MAXN]; 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++; } bool bfs(ll s, ll t, ll n) { memset(level, 0, sizeof(ll)*(n+1)); memset(gap, 0, sizeof(ll)*(n+2)); queue <ll> bfsq; level[t] = 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); } } } 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; } } } 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[u] = head[u]; --gap[level[u]]; if(gap[level[u]] == 0) { level[s] = n + 1; } relabel(u, n); ++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+1,使得这些再也无法推流到汇点的节点的余流尽快推送回源点,从而减少重贴标签的操作。
HLPP 算法复杂度为 O(n2m)(n 为节点数,m 为边数)。
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
struct HLPP { ll cnt_edge; ll head[MAXN]; ll rflow[MAXN]; ll level[MAXN]; ll flag[MAXN]; ll gap[MAXN<<1]; 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++; } bool bfs(ll s, ll t, ll n) { memset(level, 0, sizeof(ll)*(n+1)); queue <ll> bfsq; level[t] = 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); } } } 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; } level[s] = n + 1; memset(gap, 0, sizeof(ll)*((n+1)<<1)); for(ll i = 1; i <= n; ++i) { if(level[i]) { ++gap[level[i]]; } } 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
|