P3376【模板】网络最大流 题解

· · 题解

网络最大流

序言

本篇题解提供了如何想到正确算法的思维过程，只起引导思考作用。如果想要了解 Dinic 以及其他算法，不建议参阅本文。

如果你因为这是模板题而参阅题解，建议阅读完下文关于网络的相关概念之后自行思考如何写出这道题。在这过程中，如果想到某一部分而觉得有障碍，可以往下阅读，得到启发后建议继续思考。在阅读完文字题解后建议自行编写程序。当然，本文也提供了标程以供参考。

本文部分内容参考了 oiwiki 中关于网络流的介绍。感兴趣的选手可以自行参阅。

基本概念

对于初学者，本文提供了网络流的相关概念介绍。如果你已经有一定程度上的了解，请自行跳过该部分。

网络：一个特殊的有向图，一般用符号 G 表示。通常记作 G=(V,E)，其中 V 代表所有点的集合（简称点集），E 代表所有有向边的集合（简称边集）。

源点和汇点：网络中存在两个特殊的点，分别是源点和汇点。源点无入度，可以理解成图的起点，记作 s。汇点无出度，可以理解成图的终点，记作 t。显然 s \ne t 且 s,t\in V。

容量：对于一条边 u \rightarrow v，赋予一个特殊属性容量，记作 c(u,v)。我们可以将 (u,v) \notin E 的容量设为 c(u,v)=0。

流：一个实值函数，给每条边 (u,v) 赋予一个值，称作该边上的流量，记作 f(u,v)。同时，我们定义和有流量的边相连的点有流入流量和流出流量，分别指流入该节点的流量和流出该节点的流量。我们称一个点的流出流量减去流入流量为净流。对于一个点的净流，由定义可知 f(u)= \sum _{x\in V} f(u,x)-f(x,u)。

我们希望除了源点和汇点之外，其他点的净流为 0。容易发现流有以下几种性质：

残量网络：在任意时刻，G 中所有节点和剩余容量大于 0 的边构成的子图被称为残量网络，记作 G_f=(V,E_f)，其中 E_f=\left \{ (u,v) \mid c(u,v) \neq 0 \right \}。

最大流

我们称整张图的流量为源点的净流，即 f(s)，根据定义这也相当于 -f(t)。我们记作 \lvert f(s) \rvert。而给定一张网络求其最大的流量的问题就是网络最大流，我们称作网络最大流问题。

本文介绍 Edmonds-Karp 算法解决网络最大流问题。

思路

本部分引入 Edmonds-Karp 算法。

朴素做法：

我们思考这样一个问题，既然我们要找到网络最大流，并且这个最大流事实上无法超过所有边流量之和，那么我们穷举每一个答案，在图中跑一遍验证这个答案是否能达到，二分答案优化，一定能找到最大流。

观察数据规模，显然 TLE，需要优化。思考能否把这个问题简单化。

进一步思考，答案的贡献来自于从 s 到 t 的路径。每一条路径的流量取决于这条路径上的最小容量。那么如果有路径的最小容量大于 0，这条路径一定可以对答案产生贡献。我们称这样的路径为增广路。

如果我们在残量网络中不断地搜索增广路，每次更新残量网络和最大流，直到图上不存在增广路，此时我们达到的一定是最大值！

吗？

我们注意到，在这样的过程中会有先后顺序上的问题。因为多个增广路径可能共享同一条边，而我事先并不知晓哪一条增广路对答案的贡献更大。错误的路径选择可能导致局部最优，永远无法达到全局最大流。

以下的例子或许能帮你理解这一个过程：

观察这张图片，其中 s 和 t 分别是源点和汇点，容易发现，最大流是 6。最大流流经 s \rightarrow a \rightarrow t 和 s \rightarrow b \rightarrow t，流量都是 3。那如果按照我们刚刚的想法跑增广路可能会发生什么呢？

  1. 第一次增广，选择路径 s \rightarrow a \rightarrow b \rightarrow t，此时最小容量为 \min(3,1,3)=1，那么我们更新容量。

    • 总流量 f\gets f+1。

  1. 那么接下来的增广，我们只能选择路径 s \rightarrow a \rightarrow t 和路径 s \rightarrow b \rightarrow t。最小的容量皆为 2。更新之后，我们得到没有增广路的残量网络，算法结束。

现在我们的得到的最大流 f=1+2+2=5<6。显然不是正确结果。这是因为我们先选择的 a \rightarrow b 阻塞了更优的流分配方案。

看来我们的思路暂时不能解决这个顺序问题。但是往好处想，只要解决这个问题，那么可以证明这个过程一定能让我们解决这道题。所以我们只需要思考如何解决这个问题既可。

首先我们知道，我们的问题之一在于直接对原来的网络进行修改，这个过程覆盖了之前图上的信息，导致我们无法知道这个进程是不是整体最优的。所以我们必须保留原图中每条边上的容量信息。进一步思考，我们的核心错误在于无法保证顺序的最优性，那如果我们每一条可以尝试的增广路都退回到历史版本试一遍，比较哪一项更好，就能解决顺序问题，这是不是有点像可持久化？

记下每一张图，在时空上的开销是很大的。我们需要找到一种更为便捷的方法实现上述思路。

（如果读到这里你有些许思路，可以自行尝试编写程序。下文开始介绍 Edmonds-Karp 算法。）

Edmonds-Karp 算法

通常简称为 EK 算法。

我们希望残量网络是能够“反悔” 的。为了能达到这一目的，我们在网络中引入反向边的概念，对于每一条边 (u,v)，我们建一条 (v,u)。

因为这条边实际上是不存在的，根据上文，我们这样说：

对于一条边 u \rightarrow v，赋予一个特殊属性容量，记作 c(u,v)。我们可以将 (u,v) \notin E 的容量设为 c(u,v)=0。

我们将暂且将这些边的容量设为 0。当正向边流过流量时，反向边流量增加。这相当于记下了我们可以在这条边上退回流量。还是拿刚才的图举例：

为了简化，我们此处只画出了反向边构成的图。

在第一次增广之后（和上文相同），这张图变成：

如果这张图和此时的正向图叠加（为简化，图示只叠加了 b \rightarrow a 这条边），我们有：

这张图里居然出现了一条新的增广路 s \rightarrow b \rightarrow a \rightarrow t！这条增广路的实际意义是利用 b \rightarrow a 将流量从 a \rightarrow b 退回给 a。我们得到的新图是：

这张图和我们的原来的图不一样了。继续两次增广，我们可以得到最大流 f=1+1+2+2=6 显然是正确的。

其中的核心步骤在于反向边的构建，请这样理解：反向边 b \rightarrow a 的物理意义是 —— 允许将 a \rightarrow b 的流量重新分配给 a \rightarrow t，同时释放 s \rightarrow b 的容量直接连上 t。这样子我们就能用相对较小的时空开销解决网络最大流问题。

我们重新定义残量网络：残量网络包含以下边及其残量容量 c_f：

(关键点：残量网络包含原边剩余容量的正向边和代表“反悔” 能力的反向边)。

如何证明反向边不会破坏我们原来的流量守恒性质？请注意，我们同时也说了：

  • 斜对称：f(u,v)=-f(v,u)。

那么我们只需要再编写搜索模块就可以彻底解决这个问题了，因为增广路径长度一定是单调递增的，我们用 BFS 每次找最短路径就可以了。

现在我们可以直接写出 EK 算法的代码了。如果你完全看懂了上文，强烈建议自己写出代码。

这里有一个特殊的小技巧，因为我们希望通过正向边快速求得反向边的编号，来对反向边操作，我们一般用链式前向星来存图。

在链式前向星中，正向边和反向边是前后加入图中的，所以他们的编号只差 1，而我们知道对于编号 2n，有 2n \oplus 1 = 2n+1 和 (2n+1) \oplus 1 = 2n。那么我们只需要从奇数开始编号就能通过这种方法迅速访问正向边和反向边。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+100;
int n,m,s,t;

struct Node{
    int v,w,nextt; //w表示容量
}graph[2*N]; //反向边需要开两倍空间

int cnt=1,head[N];

void add(int u,int v,int w){
    graph[++cnt].v=v;
    graph[cnt].w=w;
    graph[cnt].nextt=head[u];
    head[u]=cnt;
}

int vis[N];
struct Pr{
    int v,e; //v表示从源点到该点的上一个点，e表示从源点到该点的上一条边
}pre[N]; //用于记录增广路信息

bool bfs(){
    queue<int> q;
    memset(vis,0,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    vis[s]=1;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=graph[i].nextt){
            int v=graph[i].v;
            if(vis[v]) continue;
            if(graph[i].w==0) continue; //容量为0，无法通行
            pre[v].v=u; //记下增广路上所有的点
            pre[v].e=i; //记下增广路上所有的边
            if(v==t) return true;
            vis[v]=1;
            q.push(v);
        }
    }
    return false;
}

int EK(){
    int ans=0;
    while(bfs()){
        int minn=INT_MAX;
        for(int i=t;i!=s;i=pre[i].v)
            minn=min(minn,graph[pre[i].e].w); //minn记录下增广路上最多能流过的流量
        for(int i=t;i!=s;i=pre[i].v)
            graph[pre[i].e].w-=minn,
            graph[pre[i].e^1].w+=minn;
        ans+=minn;
    }
    return ans;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n>>m>>s>>t;
    for(int i=1,u,w,v;i<=m;i++){
        cin>>u>>v>>w;
        add(u,v,w);
        add(v,u,0); //建反向边
    }
    int ans=EK();
    cout<<ans;
    return 0;
}

上述算法每次 BFS 的时间复杂度是 O(E)，最坏情况下每次增广只消除一单位流量，最多进行 O(VE) 次增广，所以 EK 算法的时间复杂度是 O(VE^2)，读者可自行参阅 oiwiki 上的相关证明。这个复杂度足以通过本题，但在稠密图中表现不佳。本篇题解只起到引导思考作用，故不介绍其他算法，有兴趣的读者请参阅 Dinic 算法和 ISAP 算法。