最大流 - お前はどこまで見えている

1. 简介

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

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

2. 增广路算法

剩余容量
剩余容量 $c_f(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)$ （ $n$ 为节点数， $m$ 为边数）。

#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(n^2m)$ （ $n$ 为节点数， $m$ 为边数）。在稀疏图上，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;
    }
};
#endif

2.3 ISAP 算法

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

距离
当前节点到汇点的最短路径长度（边权值视为 1 ）。类似于 Dinic 算法中的层次深度的计算，不过是在反图上从汇点到源点进行 BFS 。
断层
$gap[i]$ 数组用来统计距离为 $i$ 的节点个数。如果增广到某一距离发现节点数为零，需要重新计算所有节点的距离并计算 gap ；如果重新计算后仍然无法增广，则说明源点和汇点之间出现了断层，此时算法结束。

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

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

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

#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 + 1$ ，使得这些再也无法推流到汇点的节点的余流尽快推送回源点，从而减少重贴标签的操作。

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

#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

Technique ACM 算法图论网络流

Technique ACM 算法图论网络流网络流算法

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议，转载请注明出处！

最大流上一篇

PAT「1003 Universal Travel Sites (35分)」下一篇