最大流
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 的边构成的子图，即
\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(nm^2)（nnn 为节点数，mmm 为边数）。
#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;
}
};
#endif2.2 Dinic 算法
可以看出，EK 算法存在以下明显不足：
- 一次 BFS 只增广一次，如果残量网络中还存在增广路则被浪费了
- 对于已经没有剩余容量的边，EK 算法仍然进行增广判断从而导致时间上的浪费
层次深度
当前节点到源点的最短路径长度（边权值视为 1 ）。
Dinic 算法则巧妙解决了 EK 算法的不足之处：
- 一次 BFS 后使用 DFS 进行多次增广
- DFS 多次增广过程中，对于已经没有容量的边，采用弧优化的方法巧妙避免重复增广判断
Dinic 算法的复杂度为 O(n^2m)（nnn 为节点数，mmm 为边数）。在稀疏图上，Dinic 算法和 EK 算法相差不大，但在稠密图上（二分匹配之类的）Dinic的优势很明显。
#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;
}
};
#endif2.3 ISAP 算法
SAP 算法引入了断层的优化方法：
- 距离
当前节点到汇点的最短路径长度（边权值视为 1 ）。类似于 Dinic 算法中的层次深度的计算，不过是在反图上从汇点到源点进行 BFS 。
- 断层
gap[i] 数组用来统计距离为 i 的节点个数。如果增广到某一距离发现节点数为零，需要重新计算所有节点的距离并计算 gap ；如果重新计算后仍然无法增广，则说明源点和汇点之间出现了断层，此时算法结束。
SAP 算法复杂度为O(n^2m)（nnn 为节点数，mmm 为边数）。
- ISAP 算法即为 SAP 算法的优化版本，在 SAP 算法基础上加上了当前弧优化和分层优化（即 DFS 后不需要重跑 BFS 来进行分层）。
ISAP 算法复杂度为 O(n^2m)（nnn 为节点数，mmm 为边数）。
#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;
}
};
#endif3. 预流推进算法
预流推进算法的主要思想是允许水在非源汇点的节点中暂时存储，然后每个节点都尽可能将自身的超额流推送出去，并且保证在算法结束后所有非源汇点的超额流都为0，那这种方案就是合法的。
- 超额流
存储在非源汇点中的流称作这个点的超额流。
3.1 HLPP 算法
HLPP 算法的主要思想如下：
- 对于非源汇点的层次深度，每次选择层次深度最大的节点进行推流
- 如果节点推流后还有余流，则对该节点重贴标签后抬高其高度，回到上一步骤
- 直到所有非汇源点的余流都等于零，程序结束
GAP 优化
- 当出现断层后，直接将断层以上深度的所有节点的层次深度设为 n+1，使得这些再也无法推流到汇点的节点的余流尽快推送回源点，从而减少重贴标签的操作。
HLPP 算法复杂度为 O(n^2 \sqrt{m})（nnn 为节点数，mmm 为边数）。
#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本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-08-14，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
云直播
云直播（Cloud Streaming Services，CSS）为您提供极速、稳定、专业的云端直播处理服务，根据业务的不同直播场景需求，云直播提供了标准直播、快直播、云导播台三种服务，分别针对大规模实时观看、超低延时直播、便捷云端导播的场景，配合腾讯云视立方·直播 SDK，为您提供一站式的音视频直播解决方案。