最大流重制版

2023-06-19

OI 知识>图论

7.8k words

最大流

前置知识：网络流概览，请确保已熟悉网络流相关概念以及流的性质。

两大核心算法：Ford-Fulkerson 增广与Push-Relabel 预流推进算法

一，概览

对于一个给定网络，有许多合法的流函数 $f$，其中使整个网络的流量 $\sum_{(s,v)\in E}f(s,v)$ 最大的流函数被称为网络的最大流，此时的流量被称为网络的最大流量。

二，Ford-Fulkerson 增广

该方法运用贪心思想，通过寻找增广路来更新并求解最大流。

对于一张初始流量为 $0$ 的零流网络 $G$，找其最大流，核心的思想就是不断找从源点 $s$ 到汇点 $t$ 的路径，直到没有可行选择，这个过程被称为增广。

我们将 $G_f$ 上一条从源点 $s$ 到汇点 $t$ 的路径称为增广路。对于一条增广路，我们给每一条边 $(u,v)$ 都加上等量的流量，以令整个网络的流量增加，这一过程被称为增广。

由此，最大流的求解可以被视为若干次增广分别得到的流的叠加。

值得注意的是，根据流的斜对称性，$f(u,v)=-f(v,u)$，于是当我们给 $f(u,v)$ 增加一个流量时，$f(v,u)$ 也应减少等量的流量，该操作被称为退流。

解释

在最大流的实现过程中，需要经常进行访问反向边的操作，一条边和它的反向边都加等量流量，相当于这一条边未被访问过，通过访问反向边，我们可以在找到更优方案的时候进行退流操作，从而更新答案。具体内容请见下文示例。

通过这个例子，我们能看出，退流操作带来的“抵消”效果可以更新更优答案，只要存在增广路，就可以令其总流量增加，直到找不到增广路，总流量达到最大。

总结一下 Ford-Fulkerson 增广的步骤：

初始化图中流的值；
在残量网络中找到增广路；
增加总流量，并重复步骤 2-3 直到不存在增广路为止。

Ford-Fulkerson 增广正确性证明

首先引入割的概念（在最小割中还会详细讲）：定义一个网络流的割为一种点的划分方式 $(S,T)$，其中 $S\cap T=\varnothing$，$S\cup T=V$，$s\in S$，$t\in T$。即在一张网络中使源点和汇点不连通的切割（删边）方案。

割的净流量：$f(S,T)=$ $\sum_{u\in S}\sum_{v\in T}f(u,v)-$ $\sum_{u\in S}\sum_{v\in T}f(v,u)$；

割的容量：$c(S,T)=$ $\sum_{u\in S}\sum_{v\in T}c(u,v)$

引入一个引理：设 $f$ 为流网络中的一个流，横跨任何切割的净流量都相同，且都为网络的流量，即都为 $|f|$，即 $|f|=f(S,T)$。

引理的证明

可以从流的定义直观理解：网络流中 $f$ 的值是从 $s$ 流出的流量之和，给出任意切割，这些流量都经过该切割，于是割的流量即整个网络的流量。下面为数学证明.

根据流量守恒特性可以得到 $\forall u\in V-\{s,t\}$，$\sum_{v\in V}f(u,v)-$ $\sum_{v\in V}f(v,u)=$ $0$。

根据流的定义，$|f|=$ $\sum_{v\in V}f(s,v)-$ $\sum_{v\in V}f(v,s)$。

变形，得：

$|f| = $ $\sum_{v \in V}f(s,v) -$ $\sum_{v \in V}f(v,s) +$ $\sum_{u \in S-\{s\}}(\sum_{v \in V}f(u,v) -$ $\sum_{v \in V}f(v,u))$

$|f| = $ $\sum_{v \in V}f(s,v) -$ $\sum_{v \in V}f(v,s) +$ $\sum_{u \in S-\{s\}}\sum_{v \in V}f(u,v) -$ $\sum_{u \in S-\{s\}}\sum_{v \in V}f(v,u)$

$|f| = $ $\sum_{v \in V}(f(s,v) +$ $\sum_{u \in S-\{s\}}f(u,v)) -$ $\sum_{v \in V}(f(v,u) +$ $\sum_{u \in S-\{s\}}f(v,u))$

$|f| = $ $\sum_{v \in V}\sum_{u \in S}f(u,v) -$ $\sum_{v \in V}\sum_{u \in S}f(v,u)$

$|f| = $ $\sum_{v\in V-S}\sum_{u \in S}f(u,v) +$ $\sum_{v\in S}\sum_{u\in S}f(u,v) -$ $(\sum_{v\in V-S}\sum_{u\in S}f(v,u) +$ $\sum_{v\in S}\sum_{u\in S}f(v,u))$

$|f| = $ $(\sum_{v\in T}\sum_{u \in S}f(u,v) -$ $\sum_{v\in T}\sum_{u\in S}f(v,u)) +$ $( \sum_{v\in S}\sum_{u\in S}f(u,v) -$ $\sum_{v\in S}\sum_{u\in S}f(v,u))$

即：$|f|=$ $f(S,T)+0=$ $f(S,T)$，证毕。

由任意横跨切割的流量等于网络的流量，又有横跨任意切割的流量不大于切割的容量，可知，网络的流量不大于任意切割的容量，即 $f(S,T)\leq c(S,T)$，$\forall c(S,T)$。

于是一个网络最大流的值就等于最小切割的容量，这就是最大流-最小割定理。

现在我们回到对增广正确性的证明。形式化地表示增广的结束条件为：残量网络 $G_f$ 不包含任何增广路。而我们要证明的就是在这一条件下得到的 $f$ 是原网络 $G$ 的一个最大流。

首先，若残量网络 $G_f$ 不包含任何增广路，则其可被划分为两部分 $(S,T)$，其中 $S$ 定义为在 $G_f$ 中存在一条由 $s$ 到 $v$ 路径的 $v$ 的集合，$T=V-S$。对于 $\forall u\in S$，$\forall v\in T$：

$f(u,v)=c(u,v)$：如果该条件不成立，那么 $G_f$ 中必然还存在 $s$ 到 $t$ 的通路，此时未完成增广；
$f(v,u)=0$：对于 $(v,u)\notin E$，该结论显然，对于 $(v,u)\in E$，若 $f(v,u)\neq 0$，则 $G_f$ 中还存在一条 $(u,v)$ 的路径，与 $u\in S$，$v\in T$ 矛盾。

结合割的净流量：$f(S,T)=$ $\sum_{u\in S}\sum_{v\in T}f(u,v)-$ $\sum_{u\in S}\sum_{v\in T}f(v,u)$，得：

$f(S,T)=$ $\sum_{u\in S}\sum_{v\in T}f(u,v)-$ $0$；
$f(S,T)=$ $\sum_{u\in S}\sum_{v\in T}c(u,v)-$ $0=$ $c(S,T)$。

于是 $f(S,T)=c(S,T)$，而 $|f|=f(S,T)$，则 $|f|=c(S,T)$。

发现在这里 $|f|=c(S,T)$ 取到了等号，说明 $c(S,T)$ 是原网络的最小切割，否则若存在更小切割，$|f|$ 将会大于 $c(S,T)$。于是 $|f|$ 为原网络的最大流，Ford-Fulkerson 增广正确性证明完毕。

时间复杂度上界：$O(|E||f|)$，单轮增广的时间复杂度是 $O(|E|)$，而增广轮数不可能超过 $|f|$。

接下来将介绍两个 Ford-Fulkerson 增广的主流实现方式：EK 算法和 Dinic 算法。以及一个比较快但并不主流的实现方式：ISAP 算法。

Edmonds-Karp 算法

$O(nm^2)$

算法流程：

如果在 $G_f$ 上我们可以从 $s$ 出发 BFS 到 $t$，则我们找到了新的增广路。
对于增广路 $p$，我们计算出 $p$ 经过的边的剩余容量的最小值 $\Delta=\min_{(u,v)\in p}c_f(u,v)$。我们给 $p$ 上的每条边都增加 $\Delta$ 的流量，并给它们的反向边退掉 $\Delta$ 的流量，此时最大流增加了 $\Delta$。
修改流量后我们得到了新的 $G_f$，在新的 $G_f$ 中重复上述过程直到增广路不存在。

参考代码：

vector版本

变量声明与初始化：

int n,m;    // n：点数，m：边数
int a[maxn],p[maxn];    // a：BFS到 x 的最大流，p：BFS中 x 的前驱
struct Edge {int from,to,cap,flow;};    // cap：容量，flow：流量
vector<Edge> edge;    // edge：所有边的集合
vector<int> id[maxn];    // id：x 相邻所有点的下标
void init(int n)
{
    for(int i=0;i<n;i++) id[i].clear();
    edge.clear();
}

建图

void addin(int from,int to,int cap)
{
    edge.push_back({from,to,cap,0});
    edge.push_back({to,from,0,0});
    m=edge.size();
    id[from].push_back(m-2);
    id[to].push_back(m-1);
}

BFS求最大流

int maxflow(int s,int t)
{
    int flow=0;
    while(1)
    {
        memset(a,0,sizeof(a));
        queue<int> q;
        q.push(s),a[s]=inf;    //源点自己到自己流量正无穷
        while(!q.empty())
        {
            int u=q.front(); q.pop();
            for(int i=0;i<id[u].size();i++)    //遍历临点
            {
                Edge e=edge[id[u][i]];
                if(a[e.to]||e.flow>=e.cap) continue;    //搜过或已饱和
                p[e.to]=id[u][i];    //记录前驱，方便回溯
                a[e.to]=min(a[u],e.cap-e.flow);    //向下赋流，求前缀最小值
                q.push(e.to);
            }
            if(a[t]) break;    //汇点接到流，增广成功
        }
        if(!a[t]) break;    //找不到增广路了
        for(int u=t;u!=s;u=edge[p[u]].from)
        {
            edge[p[u]].flow+=a[t];    //正向路径增加
            edge[p[u]^1].flow-=a[t];    //反向路径减小
        }
        flow+=a[t];
    }
    return flow;
}

链式前向星版本

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,u,v,w,maxflow;
int a[1000],p[1000],vis[1000];
int cnt,head[1000];
struct Edge {int to,nxt,cap,flow;} edge[100005];
void addin(int x,int y,int z)
{
    edge[++cnt]={y,head[x],z,0};
    head[x]=cnt;
    edge[++cnt]={x,head[y],0,0};
    head[y]=cnt;
}
bool bfs(int s,int t)
{
    memset(vis,0,sizeof(vis));
    queue<int> q;
    q.push(s),a[s]=0x3f3f3f3f;
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=edge[i].nxt)
        {
            Edge e=edge[i];
            if(vis[e.to]||e.flow>=e.cap) continue;
            p[e.to]=i,a[e.to]=min(a[u],e.cap-e.flow);
            q.push(e.to),vis[e.to]=1;
            if(e.to==t) return 1;
        }
    }
    return 0;
}
void update(int s,int t)
{
    for(int u=t;u!=s;u=edge[p[u]^1].to)
    {
        edge[p[u]].flow+=a[t];
        edge[p[u]^1].flow-=a[t];
    }
    maxflow+=a[t];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>s>>t,cnt=1;
    for(int i=1;i<=m;i++)
        cin>>u>>v>>w,addin(u,v,w);
    while(bfs(s,t)) update(s,t);
    cout<<maxflow<<endl;
    return 0;
}

但是在某些情况下 EK 算法极其低效，其原因是：

某些边被反复搜到又被反复退流；
每次只能搜到一条增广路，各次搜索之间相互独立。

于是我们考虑使用新的算法。

Dinic 算法

$O(n^2m)$

算法思想：

从上文中 EK 低效的原因出发：

针对第一点，发现每次去寻找最短增广路，可以避免绕路，从而也不会反复经过同一条边，此处的“短”，指经过的边数，而不指容量。我们可以想到对残量网络 BFS 分层，这样就能找到最短的增广路径。

针对第二条，发现建立分层图之后我们可以使用 DFS 对增广路进行搜索，每次找到增广路后回退到分叉点，可继续寻找下一条增广路，从而一次找到多条。

系统地阐述 Dinic 算法：

考虑在增广前先对 $G_f$ 做 BFS 分层，即根据结点 $u$ 到源点 $s$ 的距离 $d(u)$ 把结点分成若干层。令经过 $u$ 的流量只能流向下一层的结点 $v$，即删除 $u$ 向层数标号相等或更小的结点的出边，我们称 $G_f$ 剩下的部分为层次图。形式化地，我们称 $G_L$ 是 $G_f$ 的层次图，其中 $E_L = $ ${ (u, v) $ $| (u, v) E_f, $ $d(u) + 1 = $ $d(v) \}$。

如果我们在层次图 $G_L$ 上找到一个最大的增广流 $f_b$，使得仅在 $G_L$ 上是不可能找出更大的增广流的，则我们称 $f_b$ 是 $G_L$ 的阻塞流。直观上理解阻塞流为在层次图的残量图中使得 $s$ 与 $t$ 不连通的那个最大增广流。

算法流程：

在 $G_f$ 上 BFS 出层次图 $G_L$。
在 $G_L$ 上 DFS 出阻塞流 $f_b$。
将 $f_b$ 并到原先的 $f$ 中去。
重复以上过程直到不存在 $s$ 到 $t$ 的路径。

此时 $f$ 即为最大流。

优化：

弧优化：

如果某一时刻我们已经知道边 $(u,v)$ 已经增广到极限（边 $(u,v)$ 已无剩余容量或 $v$ 的后侧已增广至阻塞），则 $u$ 的流量没有必要再尝试流向出边 $(u,v)$。据此，对于每个结点 $u$，我们维护 $u$ 的出边表中第一条还有必要尝试的出边。称维护的这个指针为当前弧，称这个做法为当前弧优化。
多路增广：

如果我们在层次图上找到了一条从 $s$ 到 $t$ 的增广路 $p$，则接下来我们未必需要重新从 $s$ 出发找下一条增广路，而可能从 $p$ 上最后一个仍有剩余容量的位置出发寻找一条岔路进行增广。

需要注意，弧优化是用于保证 Dinic 算法正确性的一部分，而多路增广只是一个不影响复杂度的常数优化。

复杂度分析

（参考文献：《浅谈基于分层思想的网络流算法》——王欣上 2007国家集训队论文）

首先我们需要重新审视“层次图”的概念：一个点的层次即它在残量网络中到源点 $s$ 的最短路；层次图即是建立在残量网络中的最短路图。

Dinic 算法的复杂度可以分为建立层次图和找增广路两部分。首先分析建立层次图的复杂度。

在这里我们需要给出一个定理：对于有 $n$ 个点的流量网络，层次图最多被建立 $n$ 次。证明如下：一张网络中的边可以被划分为如下类型：一种是层次图中的边，一种是从某个层次较高的点出发连向层次较低的点的边，可以证明不会存在从某个点出发连向层次比它高且高度差大于 $1$ 的点的边，因为如果存在这样的边，便不满足层次图是“最短路图”的性质了。当我们对一条增广路径增广后，会删除一条或多条增广路径中的饱和边，并向剩余图给反向边增流，相当于我们会删去一些第一类边，并增添一些第二类边。找到阻塞流后，不存在从源点到汇点的增广路了，这时我们回看整个残量网络，如果还存在源点到汇点的路径，一定是从原点出发，沿第一类边走到某一点后跳转至第二类边，之后又走第一类边直到汇点，如果此前层次图的层数为 $k$，这条新找到的路径由于经过了第二类边，相当于在层次图中逆层跳转，此时这条路路径的长度一定大于 $k$，于是我们可得层次图中的增广路长度随阶段严格递增，而在 $n$ 个点的图中，增广路的最短长度是 $1$，最长长度是 $n-1$（链），还需要注意最后还会构建一次汇点不在图中的层次图来判定算法结束，所以层次图最多被构建 $n$ 次，换而言之，Dinic 算法最多有 $n$ 个阶段。

接下来分析一个阶段中找增广路的复杂度。

注意到每增广一次，层次图中必定有一条边被删除（满流或者后侧增广至阻塞流，这一条件与当前弧优化中弧指针转移条件相同，于是所谓删除就是指当前弧优化中弧指针的移动）。层次图中最多有 $m$ 条边，所以增广最多进行 $m$ 次，在 DFS 遍历时，存在前进与后退两种操作，如果当前路径的最后一个顶点能够继续扩展，则一定是沿着上文提及的层次图第一类边向汇点前进了一步。因为增广路径长度最长为 $n$，所以最多连续前进n步后就会遇到汇点，于是单次前进时间复杂度为 $O(n)$，类似地一次增广后在增广路中后退的时间复杂度上界也是 $O(n)$，所以一个阶段中寻找增广路的复杂度是 $O(m\times (n+n))=$ $O(mn)$。

综合上述两个阶段，Dinic 的时间复杂度是阶段数 * 某阶段增广复杂度即为 $O(n^2m)$。

参考代码：

vector版本

变量声明与初始化：

int n,m,s,t;
int maxflow;
int dep[maxn];
struct Edge {int from,to,cap,flow;};
vector<Edge> edge;
vector<int> id[maxn];

建图

void addin(int x,int y,int z)
{
    edge.push_back({x,y,z,0});
    edge.push_back({y,x,0,0});
    id[x].push_back(edge.size()-2);
    id[y].push_back(edge.size()-1);
}

BFS出层次图

int bfs(int s,int t)
{
    memset(dep,0,sizeof(dep));
    queue<int> q;
    q.push(s),dep[s]=1;
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        for(int i=0;i<id[u].size();i++)
        {
            Edge e=edge[id[u][i]];
            if(dep[e.to]||e.flow>=e.cap) continue;
            dep[e.to]=dep[u]+1,q.push(e.to);
        }
    }
    return dep[t];
}

DFS寻找流

int dfs(int u,int flow)
{
    if(u==t||!flow) return flow;
    int ret=0;
    for(int i=0;i<id[u].size();i++)
    {
        int j=id[u][i]; Edge e=edge[j];
        if(dep[e.to]!=dep[u]+1||e.flow>=e.cap) continue;
        int d=dfs(e.to,min(flow-ret,e.cap-e.flow));
        if(!d) dep[e.to]=0;
        ret+=d,edge[j].flow+=d,edge[j^1].flow-=d;
        if(ret==flow) return ret;
    }
    return ret;
}
void dinic()
{
    while(bfs(s,t))
        maxflow+=dfs(s,0x3f3f3f3f);
}

链式前向星版本

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,u,v,w,maxflow,dep[1000],cur[1000];
int cnt,head[1000];
struct Edge {int to,nxt,cap,flow;} edge[100005];
void addin(int x,int y,int z)
{
    edge[++cnt]={y,head[x],z,0};
    head[x]=cnt;
    edge[++cnt]={x,head[y],0,0};
    head[y]=cnt;
}
bool bfs(int s,int t)
{
    memset(dep,0,sizeof(dep));
    queue<int> q;
    q.push(s),dep[s]=1;
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=edge[i].nxt)
        {
            Edge e=edge[i];
            if(dep[e.to]||e.flow>=e.cap) continue;
            dep[e.to]=dep[u]+1,q.push(e.to);
            if(e.to==t) return 1;
        }
    }
    return 0;
}
int dinic(int u,int Flow)
{
    if(u==t) return Flow;
    int lst=Flow;
    for(int i=head[u];i&&lst;i=edge[i].nxt)
    {
        Edge e=edge[i];
        if(dep[e.to]!=dep[u]+1||e.flow>=e.cap) continue;
        int k=dinic(e.to,min(lst,e.cap-e.flow));
        if(!k) dep[e.to]=0;
        edge[i].flow+=k,edge[i^1].flow-=k,lst-=k;
    }
    return Flow-lst;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>s>>t,cnt=1;
    for(int i=1;i<=m;i++)
        cin>>u>>v>>w,addin(u,v,w);
    while(bfs(s,t))
    {
        int flow=dinic(s,0x3f3f3f3f);
        while(flow) maxflow+=flow,flow=dinic(s,0x3f3f3f3f);
    }
    cout<<maxflow<<endl;
    return 0;
}

ISAP 算法

首先，ISAP 基于 Dinic。

算法思想

在 Dinic 算法中，每次求完增广路中都要再跑 BFS 来分层，在某些时候不够高效，ISAP 的核心思想就是分层一次，之后再增广过程中完成重分层过程。

算法流程

先跑 BFS 对图上点进行分层，不过 BFS 方向是由 $t$ 向 $s$ （其意义参见第三步）。
增广，增广过程与 Dinic 类似，只选择层数多 $1$ 的进行增广。设 $i$ 号点的层数为 $d_i$，在结束 $i$ 号点的增广过程后，若 $i$ 的流量未全部流出，遍历残量网络中 $i$ 的所有出边，找到层数最小的出点 $j$，随后令 $d_i=d_j+1$。特别地，若残量网络中 $i$ 无出边，令 $d_i=n$（优化：最短路的修改具有连续性，即我们不需要每次求后继的标号最小值，而是直接给标号加一）。
当 $d_s\geq n$ 时，图上不存在增广路，此时可终止算法。

正确性证明

某一个点接受一定量的流量，并向外推流。

根据上面的算法步骤，当一个点推流推完的时候，这个点的层数不提高。因为此时这个点的层数已经足够其推流了，不需要再提高，而且根据算法的要求，流量只能在相邻层之间移动。

假设当前点推流推不出去，需要提高层数，当前的点无法推流了，前面的点也无法推流，因此如果我们提高了这个点的层数，前面的点也必须要提高层数（否则无法推流），此时就能够保证至少这个点接受流量不变。

提高层数后，如果后面的点有层次更高的点，就可以继续推流，存在增广路；如果没有了，都是层次比较低的点，若这些点推流完毕没法提高层次，就会出现断层，满足算法结束条件。

综上，算法正确性成立。

优化

和 Dinic 类似，ISAP 中也存在当前弧优化。

ISAP 还有另一个优化，我们记录层数为 $i$ 的点数量为 $num_i$，每当将一个点的层数从 $x$ 更新到 $y$ 时，更新 $num$ 数组的值，若更新后 $num_x=0$，意味着图中出现断层，此时无增广路，可直接终止算法，该优化被称为 GAP 优化。

代码实现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,s,t,u,v,w,cnt,head[100005],dep[100005],gap[100005];
struct Edge {int to,nxt,flow;} edge[2000005];
inline void addin(int x,int y,int w)
{
    edge[++cnt]={y,head[x],w},head[x]=cnt;
    edge[++cnt]={x,head[y],0},head[y]=cnt;
}
inline void bfs()
{
    queue<int> q;
    q.push(t),dep[t]=1,gap[1]=1;
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int v=edge[i].to;
            if(dep[v]) continue;
            q.push(v),dep[v]=dep[u]+1,gap[dep[v]]++;
        }
    }
    return;
}
ll mxf;
int dfs(int u,int f)
{
    if(u==t) {mxf+=1ll*f;return f;}
    int lst=0;
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(dep[v]+1!=dep[u]||!edge[i].flow) continue;
        int k=dfs(v,min(edge[i].flow,f-lst));
        if(k) edge[i].flow-=k,edge[i^1].flow+=k,lst+=k;
        if(lst==f) return f;
    }
    --gap[dep[u]];
    if(gap[dep[u]]==0) dep[s]=n+1;
    dep[u]++,gap[dep[u]]++;
    return lst;
}
inline int rd()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x;
}
inline void wt(ll x)
{
    if(x>9) wt(x/10);
    putchar(x%10+'0');
}
signed main()
{
    n=rd(),m=rd(),s=rd(),t=rd(),cnt=1;
    for(int i=1;i<=m;i++) u=rd(),v=rd(),w=rd(),addin(u,v,w);
    bfs();
    while(dep[s]<=n) dfs(s,0x3f3f3f3f);
    wt(mxf),putchar('\n');
    return 0;
}

二，Push-Relabel 预流推进算法

该方法在求解过程中忽略流的守恒性，每次对一个结点更新答案以求最大流。

超额流：对于一个结点，进入结点的流若超出流出结点的流，超出部分即为该结点的超额流 $e(u)$，形式化地，$e(u)=$ $\sum_{(x,u)\in E}f(x,u)-$ $\sum_{(u,y)\in E}f(u,y)$。

溢出：超额流 $e(u)>0$ 时，称结点 $u$ 溢出（不包括 $s$ 与 $t$）。

预流推进算法维护每个结点的高度 $h(u)$，并且规定溢出的结点 $u$ 如果要推送超额流，只能向高度小于 $u$ 的结点推送；如果 $u$ 没有相邻的高度小于 $u$ 的结点，那就修改 $u$ 的高度。

1. 相关操作

高度函数：维护一个高度映射 $h$。
1. $h(s)=|V|,$ $h(t)=0$
2. $\forall (u,v)\in E_f,$ $h(u)\leq h(v)+1$
称为 $h$ 是残量网络 $G_f=(V_f,E_f)$ 的高度函数。

引理：设 $G_f$ 上的高度函数为 $h$，对于任意两个节点 $u,v\in V$，如果 $h(u)>h(v)+1$，则 $(u,v)$ 不是 $G_f$ 中的边。
推送：将超额流从 $u$ 推送到 $v$。

条件：点 $u$ 溢出，点 $v$ 满足 $(u,v)\in E_f,$ $c(u,v)>f(u,v),$ $h(u)=h(v)+1$。

如果 $(u,v)$ 在推送完之后满流，将其从残量网络中删除。
重贴标签：将 $h(u)$ 更新为 $\min_{(u,v)\in E_f}h(v)+1$。

条件：结点 $u$ 溢出，且 $\forall (u,v)\in E_f,$ $h(u)<h(v)$。
初始化：
$1. \forall (u,v)\in E,$ $f(u,v)={ \begin{cases}c(u,v),u=s\\ 0,u\neq s\\ \end{cases} }$

$2. \forall u\in V,$ $h(u)={ \begin{cases}|V|,u=s\\ 0,u\neq s\\ \end{cases}\ }$

$3. e(u)=$ $\sum_{(x,u)\in E}f(x,u)-$ $_{(u,y)E}f(u,y) $

2. 过程及暴力实现

每次扫描整个图，存在结点 $u$ 满足 push 或 relabel 操作的条件则执行对应操作。

考虑暴力实现：暴力扫描是否有溢出的结点，有就更新。

变量声明及建图：略

初始化

void init()
{
    for(int i=head[s];ili=edge[i].nxt)
    {
        Edge e=edge[i];
        ex[e.to]=e.flow,ex[s]-=ex[e.to];
        edge[i].flow=0,edge[i^1].flow=e.flow;
    }
    h[s]=n;
}

推送

bool push(int i)
{
    int u=edge[i^1].to,v=edge[i].to,flow=max(ex[u],edge[i].flow);
    ex[u]-=flow,ex[v]+=flow;
    edge[i].flow-=flow,edge[i^1].flow+=flow;
    return ex[u];
}

重贴标签

void relabel(int u)
{
    h[u]=0x3f3f3f3f;
    for(int i=head[u];i;i=edge[i].nxt)
        if(edge[i].flow) h[u]=min(h[u],h[edge[i].to]);
    ++h[u];
}

3. HLPP 算法

$O(n^2\sqrt{m})$

在上述过程基础上，优先选择高度最高的溢出结点。

算法流程：

初始化
选择溢出结点中高度最高的结点并推送
如果2中的点仍溢出，重贴标签并回到2
没有溢出结点时结束

优化：

BFS 优化：

初始化时使用 BFS，初始化 $h(u)$ 为 $u$ 到 $t$ 的最短距离，特别地使 $h(s)=n$。

在BFS的同时检查连通性排除无解情况。
GAP 优化：

如果某一时刻 $h(u)=t$ 的结点个数为 $0$，将 $h(u)>t$ 的结点高度变为至少 $n+1$ 以便尽快推送回 $s$，减少重贴标签次数。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,s,t,u,v,w;
int h[2000],c[2000],num[2000];
int cnt=1,head[2000];
struct Edge {int to,nxt,val;} edge[300000];
void addin(int x,int y,int z)
{
    edge[++cnt]={y,head[x],z},head[x]=cnt;
    edge[++cnt]={x,head[y],0},head[y]=cnt;
}
int stop;
stack<int> b[2000];
bool init()
{
    memset(h,0x3f3f3f3f,sizeof(h));
    queue<int> q;
    q.push(t),h[t]=0;
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=edge[i].nxt)
        {
            int v=edge[i].to;
            if(edge[i^1].val&&h[v]>h[u]+1)
                h[v]=h[u]+1,q.push(v);
        }
    }
    return h[s]!=0x3f3f3f3f;
}
bool push(int u)
{
    for(int i=head[u];i;i=edge[i].nxt)
    {
        int v=edge[i].to;
        if(!edge[i].val||(u!=s&&h[u]!=h[v]+1)) continue;
        if(v!=s&&v!=t&&!c[v]) b[h[v]].push(v),stop=max(stop,h[v]);
        int d=(u==s)?edge[i].val:min(edge[i].val,c[u]);
        c[u]-=d,c[v]+=d,edge[i].val-=d,edge[i^1].val+=d;
        if(!c[u]) return 0;
    }
    return 1;
}
void relabel(int u)
{
    h[u]=0x3f3f3f3f;
    for(int i=head[u];i;i=edge[i].nxt)
        if(edge[i].val) h[u]=min(h[u],h[edge[i].to]+1);
    if(h[u]>=n) return;
    b[h[u]].push(u),stop=max(stop,h[u]),++num[h[u]];
}
int findtop()
{
    while(b[stop].size()==0&&stop>-1) stop--;
    return stop==-1?0:b[stop].top();
}
int hlpp()
{
    if(!init()) return 0;
    for(int i=1;i<=n;i++) if(h[i]!=0x3f3f3f3f) ++num[h[i]];
    h[s]=n,push(s);
    for(int u=findtop();u;u=findtop())
    {
        b[stop].pop();
        if(!push(u)) continue;
        --num[h[u]];
        if(!num[h[u]]) 
            for(int i=1;i<=n;i++)
                if(i!=s&&i!=t&&h[i]>h[u]&&h[i]<=n) h[i]=n+1;
        relabel(u);
    }
    return c[t];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
        cin>>u>>v>>w,addin(u,v,w);
    cout<<hlpp()<<endl;
    return 0;
}

三，习题

若无特殊情况，所有习题均只给出主函数建图代码，其余代码套用模板

洛谷P1343 地震逃生

每次通过的人数即为最大流，通过的批次即为总人数与单次人数之商上取整。当最大流为 $0$ 的时候，说明无法逃离至 $n$ 点，此时输出无解即可。

code

n=rd(),m=rd(),x=rd()；
s=1,t=n,cnt=1;
for(int i=1;i<=m;i++)
    u=rd(),v=rd(),w=rd(),addin(u,v,w);
...
if(mxf==0) cout<<"Orz Ni Jinan Saint Cow!"<<endl,exit(0);
tot=x/mxf+(x%mxf?1:0);
wt(mxf),putchar(' '),wt(tot);
return 0;

洛谷P1402 酒店之王

十分经典的建图思路，将每个客户拆为两个点，代表两个需求，一个与房间代表的点相连，容量为是否喜欢，另一个点与食物代表的点相连，容量为是否喜欢，之后建立超级源点和超级汇点，超级源点连所有房间，容量为 $1$ 代表可选但只可选一次，所有食物连向汇点，容量也为 $1$，求最大流即可。

code

n=rd(),p=rd(),q=rd(),s=0,t=2*n+p+q+1,cnt=1;
for(int i=1;i<=p;i++) addin(s,i,1);
for(int i=1;i<=n;i++)
	for(int j=1;j<=p;j++)
		w=rd(),addin(j,i+p,w);
for(int i=1;i<=n;i++) addin(i+p,i+p+n,1);
for(int i=1;i<=n;i++)
	for(int j=1;j<=q;j++)
		w=rd(),addin(i+p+n,j+p+2*n,w);
for(int i=1;i<=q;i++) addin(i+p+2*n,t,1);

洛谷P3254 圆桌问题

此题可以贪心，但在此不做讲解。

考虑将各单位与桌子相连，边权为 $1$ 代表该单位至多派一个人到该桌子，之后建立超级源汇点，将源点与单位连，容量为人数，桌子与汇点连，容量为可容纳人数，之后跑最大流即可。若最大流不等于总人数，说明无解。统计方案时对于每个单位遍历其出边，发现饱和边后输出对应桌子即可。

code

m=rd(),n=rd(),s=0,t=n+m+1,cnt=1;
for(int i=1;i<=m;i++) w=rd(),addin(s,i,w),sum+=w;
for(int i=1;i<=m;i++)
	for(int j=1;j<=n;j++)
		addin(i,j+m,1);
for(int i=1;i<=n;i++) w=rd(),addin(i+m,t,w);
...
if(mxf!=sum) putchar('0'),exit(0);
putchar('1'),putchar('\n');
for(int i=1;i<=m;i++)
{
	for(int j=head[i];j;j=e[j].nxt)
		if(e[j].flow==0) wt(e[j].to-m),putchar(' ');
	putchar('\n');
}
return 0;

洛谷P4174 最大获利

首先对某一个用户群中，只有同时选中两个中转站才有获益，一件事要发生，它需要的所有前提条件也要发生，在图论中这种任意点的任意后继一定在图中的图叫闭合图，此题即为一个最大权闭合图问题，建立一个超级源点和超级汇点，将源点连向所有中转站，容量为建造费用，将用户群转化为点，连向超级汇点，容量为获益。原图中的边容量为正无穷，跑一遍最大流。一条由源点向汇点的增广路可以被分为三段：源点-中转站，中转站-用户，用户-汇点，其中中转站-用户容量为正无穷，对最大流没有贡献，考虑剩下两段中哪段成为了该条增广路的最大流。如果源点-中转站是最大流，相当于收益大于代价，此时要建造中转站；如果用户-汇点是最大流，相当于代价大于收益，此时不建造中转站。先求出所有用户群都选中的总收益，回看以上两种情况，对于前者，付出了中转站的建造代价，可以看作总收益中的损失；对于后者，失去了该用户群的收益，也可以看作是总收益的损失。推广到整个图中，最终答案就是总收益与最大流的差值。

code

cin>>n>>m,s=0,t=n+m+1,cnt=1;
for(int i=1;i<=n;i++) cin>>p,addin(s,i,p);
for(int i=1;i<=m;i++)
{
	cin>>u>>v>>w,sum+=w;
	addin(i+n,t,w),addin(u,i+n,inf),addin(v,i+n,inf);
}
...
cout<<sum-maxflow<<endl;

Categories

Tags

Archives

Recent Posts

最大流重制版

最大流

一，概览

二，Ford-Fulkerson 增广

Edmonds-Karp 算法

算法流程：

参考代码：

vector版本

链式前向星版本

Dinic 算法

算法思想：

算法流程：

优化：

复杂度分析

参考代码：

vector版本

链式前向星版本

ISAP 算法

算法思想

算法流程

优化

代码实现

二，Push-Relabel 预流推进算法

1. 相关操作

2. 过程及暴力实现

3. HLPP 算法

算法流程：

优化：

参考代码：

三，习题

洛谷P1343 地震逃生

洛谷P1402 酒店之王

洛谷P3254 圆桌问题

洛谷P4174 最大获利