网络最大流 学习笔记&详解

· · 算法·理论

网络流入门：网络最大流

友情提示：请学完图论基本知识再来阅读此篇文章。 这里只有 dfs 求解（Ford），EK 和 Dinic，没有什么神仙 HLPP，因为作者太菜了自己也不会（ 文章也是智障作者学完之后口糊的（ 只是感觉网络流这个东西挺有意思的 虽然又感觉用处不大。

前置知识

网络是指一张特殊的有向图，图中每条边 (u,v)\in E 都有一个容量 cap，记为 c(u,v)。如果 (u,v)\notin E，可以将 c(u,v) 视为 0。图中还有两个特殊的点：源点 s 和汇点 t。

在一张网络 G 中，流是一个从边集 E 到整数集或实数集的函数，这里先给出流的概念/定义，读者在网络流的学习中会更加深刻地体会到什么是流。 形象化的讲，你可以认为从源点 s 会流出一些流量，通过图上的边，最终流入 t，就像水流一样。 流则指的就是这条“水流”。

流的性质：

  1. 对于图 G 中每条边 (u,v)\in E 的流量 f(u,v) 表示从这条边流经了多少流量，其中 0\le f(u,v)\le c(u,v)，即从该条边流过的流量的不能超过该条边的容量。
  2. 对于图上任意一个节点 u，设流入的流量为 in_u，流出的为 out_u，如果 u 不是源汇点（中间点），那么 in_u=out_u；in_s=0，out_t=0，out_s=in_t。即从 s 流出的流量全部会流入 t，不会留在中间点。

最大流问题

最大流问题很容易理解：给你一张网络，求出最多可以从 s 流出多少流量流进 t。

我们可以提出一个设想：我们随便通过搜索找到一条还可以继续流出流量的路径，把这条路径上的流量增满，也就是路径上每条边都加上这条路径上最小的 c(u,v)-f(u,v)，重复这个过程，直到找不到路了，此时流出的总流量便是答案。 然后就很快会被 hack。例：

这张图上，答案应为 6，先沿着 s \to2\to t 这条路径流出 1 的流量。我们称这种从 s\to t 的路径为增广路。流出 2 可被称为增广 2。继续，再沿着 s\to1\to3\to t 增广 4，沿着 s\to 1\to 2 \to t 再增广 1。请注意每增广一次 f(u,v) 的值都会有所改变，这个值不能大于 c(u,v)。记这条增广方式产生的流为 f_1。

1：

如果按我们上面那个贪心思路，我们可能会找到一条错误的增广方式 s\to 1\to2\to t，沿着这条路径增广 2，再沿着 s\to1\to3\to t 增广 3，得到错误答案 5。同样的。记这条增广方式产生的流为 f_2。

2（路就没画了，自己脑补吧QwQ）：

所以这个贪心思路是错的。不过，我们可以改进它。 怎么办？我们看一下两种增广方式中每条边的流量 f(u,v) 的差，设 f_3(u,v)=f_1(u,v)-f_2(u,v)：

我们可以看见，我们在 1\to2 这里少流了 1 的流量，但是在 s\to2 和 1\to3\to t 这两条路上多流了 1 的流量。

下面就是最重要的一点：我们可以把它看作沿着 1\to2 的反边 2\to1 回推了 1 点流量。

具体一点，我们先沿着 s\to1\to2\to t 增广了 2，但这是错的，于是我们再沿着 s\to 2\to 1\to 3\to t 这里增广了 1，其中 2\to1 这条边是 1\to2 的反边，沿着这条边将错增广的 1 点流量推了回去。

至此，我们有了一个新的贪心思路：对于原图上每条边都建一条反边，按原来的方式增广，每增广一条边 (u,v)，都将这条边的反边 (v,u) 的剩余容量 f(v,u) 减去 1。有时为了方便，代码中我们将每条边的容量重新定义为从该条边还能流多少流量。原图上的每条边 (u,v) 容量的初始值为输入的 c(u,v)，自己加的反边 (v,u) 容量初始值为 c(v,u)=0。

这是对的吗？答案是肯定的。如果要证明，我们则不得不延伸至最大流最小割定理。读者可以先确保消化掉了上面的知识再往下读。

最小割的定义：在一张网络上去掉一些边，使得所有点都被划分为了两个点集，源汇点位于不同的集合中。问去掉的边的容量之和最小是多少。最小割指去掉的边集，最小割的容量就是这个问题的答案。

最大流最小割定理：一张网络的最大流量 = 这张网络最小割的容量。

假设我们已经跑出了这张网络的最大流，那么这张图上就不存在增广路了，也就是说去掉满流的边图就被分割成了两部分。如果得到的流不是最大流，说明这张图上仍然存在增广路，去掉满流的边网络仍然连通。没有跑满最大流的网络中满流的边不能组成割。所以，一张网络的最大流量 \le 最小割。

残量网络指的是任意时刻原网络去除满流的边后剩余的网络。

假设在跑完最大流之后的残量网络中，源点 s 可达的点构成的点集为 V_1，其余点构成点集 V_2。由于 s\in V_1，最大流会从 V_1 流出，换句话说，最大流量 = 从 V_1 流出到 V_2 的流量 - 从 V_2 流回 V_1 的流量 = 流出 V_1 的流量 - 流入 V_1 的流量。

我们知道所有从 V_1 连到 V_2 的边 (u,v) 都被去除了，它们是满流的，f(u,v)=c(u,v)，否则可以沿着这条边到 V_2。可知道对于这些边的反向边 (v,u)，也就是从 V_2 连到 V_1 的边，f(u,v)=0。

所以流出 V_1 的流量 - 流入 V_1 的流量 = 去除的边的容量和 = 最大流量。不难想到上述求解最大流的算法是正确的。

证毕。

Ford–Fulkerson 增广

Ford-Fulkerson 增广是通过增广路求最大流一类算法的统称，这类算法通过每次在残量网络上寻找增广路并增广求解最大流。 Ford-Fulkerson 有很多种实现方式，例如最简单的 dfs 寻找增广路，bfs 寻找增广路（即 EK 算法）。

dfs 实现

dfs 的实现很简单，dfs 遍历整个图，如果找到一条增广路则立刻回溯停止搜索。

时间复杂度为 O(mF)，F 为最大流量。

时间复杂度很不优秀，T 了（悲）。

核心代码：

const int INF=0x3f3f3f3f;
int n,m,s,t;
bool vis[205];//图上 dfs 标记数组
struct Edge{
    int to,cap,nxt;//cap指的是这条边的剩余容量
}e[2000005];
int head[100005],tot=1;//链前存图，tot初始化为 1 是为了方便，第 i 条边的反向边则为 i^1
void add_edge(int u,int v,int cap)
{
    e[++tot].to=v,e[tot].cap=cap,e[tot].nxt=head[u],head[u]=tot;
    //建反边
    e[++tot].to=u,e[tot].cap=0/*初始化为0是因为这条边是原图不存在的附加反向边*/,
    e[tot].nxt=head[v],head[v]=tot;
}

int dfs(int x,int flow)//dfs求增广路
{
    vis[x]=1;
    if(x==t)return flow;//找到了，返回
    for(int i=head[x];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(vis[v])continue;
        if(e[i].cap)//如果可以沿着这条边继续增广
        {
            int k=dfs(v,min(flow,e[i].cap));
            if(k)//找到一条增广路
            {
                e[i].cap-=k;//减少剩余容量
                e[i^1].cap+=k;//i的反向边i^1剩余容量增加k
                return k;//返回
            }
        }
    }
    return 0;//无法继续增广，返回0
}

int max_flow()//求解最大流
{
    int f,res=0;
    do{
        memset(vis,0,sizeof(vis));
        f=dfs(s,INF);
        res+=f;
    }while(f);//重复寻找增广路直到找不到增广路
    return res;
}

EK 算法

EK 算法全称 Edmonds-Karp 增广路算法。该算法和 dfs 十分类似：每次增广从源点 s 出发，在残量网络上通过 bfs 找到一条从 s 到 t 的最短路径。EK 算法最多需要增广 nm 次，单次增广时间复杂度为 m，所以最坏时间复杂度为 O(nm^2)。实际根本达不到这个上界。

对于 bfs 搜索路径这回事，如果要保存经过的结点，那么可以用到一个技巧，记录每一个状态的上一个状态（注意这里是哪条边），最后再通过最后一个状态一直往前回溯到初始状态。

很明显比 dfs 效率要好很多，可以 A。

核心代码：

bool vis[205];//图上 bfs 标记数组
int pre[205];//记录前驱（哪条边）
int fl[205];//到节点 i 时的可以增广的最大流量
bool bfs()//bfs搜最短路
{
    memset(vis,0,sizeof(vis));
    queue<int>q;
    q.push(s);vis[s]=1;fl[s]=INF;
    while(!q.empty())
    {
        int x=q.front();q.pop();
        for(int i=head[x];i;i=e[i].nxt)
        {
            if(e[i].cap)
            {
                int v=e[i].to;
                if(vis[v])continue;
                fl[v]=min(fl[x],e[i].cap);
                pre[v]=i;//哪条边
                q.push(v),vis[v]=1;
                if(v==t)return 1;//已经找到一条路径了，返回
            }
        }
    }
    return 0;
}
int update()//更新边的剩余容量
{
    int x=t;//当前点
    while(x!=s)
    {
        int i=pre[x];
        e[i].cap-=fl[t];
        e[i^1].cap+=fl[t];//反向边
        x=e[i^1].to;//这条边的反向边指向的节点就是前一个节点
    }
    return fl[t];
}
int max_flow()//求解最大流
{
    int res=0;
    while(bfs())res+=update();
    return res;
}

重点：Dinic 算法

如果消化了上面的两个算法，那么 Dinic 就非常好理解。

Dinic 算法是容易实现的最大流算法中效率教高的，也是求解二分图最大匹配效率最高的算法，求解二分图最大匹配的时间复杂度为 O(m\sqrt n)。

Dinic 跟 EK 类似，也是寻找最短的一条增广路，不同的是 EK 是 bfs 找到一条最短路直接更新，而 Dinic 则是先 bfs 构造分层图，再在分层图上跑 dfs 找增广路。Dinic 一次可以找到多条增广路并更新。

具体一点，在图上 bfs 跑最短路，记到点 i 的最短路为 d_i。将这张网络的点按照 d 从小到大开始分层。每次 dfs 都往更深一层搜索，找到一条增广路先不回溯，而是继续从当前节点寻找其他增广路。

我们可以给 Dinic 加上一个当前弧优化，避免多次枚举一条边。具体实现看代码。

请注意，因为用的是 dfs，所以我们如果给点打标记，每 dfs 一次都要 memset 清空 vis 数组。这会影响程序的效率，加上了当前弧优化就可以避免了。

现在的 Dinic 算法时间复杂度为 O(n^2m)。

可以看见跑的飞快

核心代码：

bool bfs()//bfs跑分层图
{
    for(int i=1;i<=n;i++)d[i]=-1;
    queue<int>q;
    q.push(s);
    d[s]=0;
    while(!q.empty())
    {
        int fr=q.front();q.pop();
        now[fr]=head[fr];//当前弧优化初始化为这个点的第一条边
        for(int i=head[fr];i;i=e[i].next)
        {
            if(e[i].cap>0&&d[e[i].v]==-1)//可以扩展
            {
                q.push(e[i].v);
                now[e[i].v]=head[e[i].v];
                d[e[i].v]=d[fr]+1;
                if(e[i].v==t)return true;//因为对于d[i]>=d[t]的点i，必定不会到达，所以可以直接返回
            }
        }
    }
    return false;
}
int dfs(int x,int f)
{
    if(x==t)return f;
    int res=0;
    for(int i=now[x];i&&f;i=e[i].next)
    {
        now[x]=i;//当前弧优化
        if(e[i].cap>0&&d[e[i].v]>d[x])
        {
            int k=dfs(e[i].v,min(f,e[i].cap));
            if(!k)d[e[i].v]=-INF;//优化2：如果从这个点无法找到增广路，让后面不在搜到这个点
            else{
                e[i].cap-=k;
                e[i^1].cap+=k;
                res+=k;f-=k;//这里剩余可以流出的流量要减少
            }
        }
    }
    return res; 
}
int max_liu()
{
    int ret=0;
    while(bfs())
        ret+=dfs(s,INF);
    return ret;
}

其他算法

还有一些算法，就不详细介绍了。

ISAP 与 Dinic 类似，只是每次寻找完一条增广路之后不会再进行 dfs，而是对这条增广路上的点进行更新。

有一种高效的预流推进算法：HLPP 算法，时间复杂度 O(n^2\sqrt m)。

THE END

希望我的文章为大家带来了帮助。