【算法】网络流之最大流问题

于由XZYQvQ发布

1. 什么是网络流

网络流 (network-flows) 是一种类比水流的解决问题方法，与线性规划密切相关。网络流的理论和应用在不断发展，出现了具有增益的流、多终端流、多商品流以及网络流的分解与合成等新课题。网络流的应用已遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等众多领域。

——摘自度娘百科

2. 什么是最大流问题

管道网络中每条边的最大通过能力（容量）是有限的，实际流量不超过容量。
最大流问题 (maximum flow problem)，一种组合最优化问题，就是要讨论如何充分利用装置的能力，使得运输的流量最大，以取得最好的效果。

——还是摘自度娘百科

通俗地说就是把图看成一个管道网络，从起点（这个是可以指定的）以一定速度灌水，问最大以多快的速度灌，水不会溢出。

3. 怎么求最大流？

1. 前言

目前我只学了增广路算法……＝￣ω￣＝

而且还是用深度优先搜索实现的增广路算法。

你要是看不起 dfs……那你就别看呀！╭（╯＾╰）╮

下面的话可能要学完了最大流才能看得懂，看不懂也是完全没关系的

我先看了看刘汝佳的小紫书，上面讲：“很容易找出让它很慢的例子”。然而我想了想也没觉得会很慢啊，每次增广最坏的复杂度是 O(N)，怎么会被卡呢……然后我又问了问神犇 pyh，他（或她或它）说 ta 一直写的是 dfs 啊。于是我抱着挑战权威的心态写出了 dfs 版的增广路算法。然后……成功了。

然后我发现各种最大流算法的代码中建图都记录了两个值：每条边的流量与每条边的流量上限，然后根据流量上线-流量得到残量。我就想：如果我只保存残量难道不行吗？然后我就实践了一下，发现的确实可以的……

所以后面的代码风格看起来可能和网上的大部分代码是不同的……

（这个故事告诉我们不要迷信！实践出真知）

2. 思路

先定义一下：
残量：对于一条边来讲，它的残量就是它的最大流量减去它当前的实际流量。

然而思路是非常简单的。
1. 建图，每条边存 3 个值：这条边的起点，终点与残量。对于每条图中的边，它的残量初始值就是它的最大流量（因为一开始所有的边的实际流量都为 0 啊）。其次，我们还要建立反向边（就是对于每条从点 u 到点 v 的边，它的反向边就是一条从 v 到 u 的边），它的残量初始值为 0。为什么呢？简单地说就是让程序有后悔的余地，就是说如果一开始把某条边的实际流量加多了，导致无法得到最大流，就可以通过反向边减回来。这后面看代码你就明白反向边是干什么用的了。

  1. 找增广路，找增广路时更新最大流。一直循环这个步骤，直到找不到增广路为止。

  2. 输出答案。

3. 具体做法

怎么找增广路？

其实就是找一条从起点到终点的路径（当然这条路径上的最小残量要>0）。对于这条路径上的每条边的流量，都加上这个路径上的最小残量（其实就是这些边的残量都减去这个路径上的最小残量），并且这些边的反向边的残量都加上这个路径上的最小残量（也就反向边的流量都减去最小残量）。

这个做法是很简单易懂的，相信聪明的你肯定琢磨一下就知道为什么要这么做了。（其实我是自己想出来的哇哈哈哈又开始飘了）

用 bfs 是可以做的。但是 dfs 不是更简单吗？代码都不知道短了多少。回溯的时候直接修改边的残量就行了。而 bfs 还需要搞个变量存每个点的前驱，真是麻烦。

还有一些详细的见代码吧。

dfs 找增广路的代码：

bool dfs(int u,int f)//u 是当前节点，f 是路径上最小残量，返回值为 1 说明成功找到增广路，返回值为 0 说明找增广路失败了
{
    if(u==n){ans+=f,pf=f;return 1;}//这里 n 是终点的编号，如果到了终点说明找到了增广路，最大流量（ans）加上路径最小残量，pf 是路径的最小残量，等下回溯的时候修改路径上的边的残量时就减去（反向边是加上）这个值
    book[u]=1;//标记当前节点
    for(int i=0;i<g[u].size();i++)//枚举下一个节点
        if(e[g[u][i]].c>0&&!book[e[g[u][i]].v])//如果下一个节点没有被访问过并且残量大于 0
            if(dfs(e[g[u][i]].v,min(f,e[g[u][i]].c)))//如果能够通过这个节点找到增广路
            {
                e[g[u][i]].c-=pf,e[g[u][i]^1].c+=pf;//当前边的残量减去路径上最小残量，反向边加上最小残量（为什么反向边的编号是当前边的编号异或 1 呢？你想我们读入图的时候，反向边肯定是接在当前边的后面存储的，编号为 0 的和 1 的是一对，2 和 3 是一对，所以是异或 1）
                return 1;//返回找到了增广路
            }
    return 0;//返回没找到增广路
}
C++
Copy

至于具体整个代码怎么搞，就看下面的模板题&代码吧！

4. 模板题&代码

1. Flow Problem HDU – 3549

传送门＝￣ω￣＝

代码：

#include <cstdio>
#include <vector>
using namespace std;
struct edge{int u,v,c;};
int t,n,m,ans,pf;
bool book[20];
vector<edge> e;
vector<int> g[20];
bool dfs(int u,int f)
{
    if(u==n){ans+=f,pf=f;return 1;}
    book[u]=1;
    for(int i=0;i<g[u].size();i++)
        if(e[g[u][i]].c>0&&!book[e[g[u][i]].v])
            if(dfs(e[g[u][i]].v,min(f,e[g[u][i]].c)))
            {
                e[g[u][i]].c-=pf,e[g[u][i]^1].c+=pf;
                return 1;
            }
    return 0;
}
int main()
{
    scanf("%d",&t);
    for(int k=1;k<=t;k++)
    {
        e.clear(),ans=pf=0;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)g[i].clear(),book[i]=0;
        for(int i=1,x,y,z;i<=m;i++)
            scanf("%d%d%d",&x,&y,&z),
            g[x].push_back(e.size()),e.push_back((edge){x,y,z}),
            g[y].push_back(e.size()),e.push_back((edge){y,x,0});
        while(dfs(1,1000000000)){for(int i=1;i<=n;i++)book[i]=0;pf=0;}
        printf("Case %d: %d\n",k,ans);
    }
    return 0;
}
C++
Copy

2. Drainage Ditches POJ – 1273

传送门＝￣ω￣＝

#include <cstdio>
#include <vector>
using namespace std;
struct edge{int u,v,c;};
int n,m,ans,pf;
bool book[205];
vector<edge> e;
vector<int> g[205];
bool dfs(int u,int f)
{
    if(u==n){ans+=f,pf=f;return 1;}
    book[u]=1;
    for(int i=0;i<g[u].size();i++)
        if(e[g[u][i]].c>0&&!book[e[g[u][i]].v])
            if(dfs(e[g[u][i]].v,min(f,e[g[u][i]].c)))
            {
                e[g[u][i]].c-=pf,e[g[u][i]^1].c+=pf;
                return 1;
            }
    return 0;
}
int main()
{
    while(~scanf("%d%d",&m,&n))
    {
        e.clear(),ans=pf=0;
        for(int i=1;i<=n;i++)g[i].clear(),book[i]=0;
        for(int i=1,x,y,z;i<=m;i++)
            scanf("%d%d%d",&x,&y,&z),
            g[x].push_back(e.size()),e.push_back((edge){x,y,z}),
            g[y].push_back(e.size()),e.push_back((edge){y,x,0});
        while(dfs(1,1000000000)){for(int i=1;i<=n;i++)book[i]=0;pf=0;}
        printf("%d\n",ans);
    }
    return 0;
}
C++
Copy
分类： 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

3 条评论

forto42 · 2020年3月2日 10:40 上午

dalao，据说这个叫 FF 算法，而且确实被 lrj 卡了

回复

    Remmina · 2020年3月2日 10:46 上午

    额？我不记得了，这不就是最简单的增广路算法嘛？
    我退役前反正学会了 dinic

    回复

Dinic算法 网络流 最大流问题 – K-XZY · 2017年4月13日 10:34 下午

[…] 算法流程： 1. 建图（同普通增广路算法一样，要建立反向弧，具体可以见我的另一篇博客：网络流之最大流问题传送门＝￣ω￣＝）2. 建立分层图（就跑一次 bfs 即可），如果 bfs 没能访问到汇点，那么结束算法。 3. 在分层图上跑普通的增广路算法，然后返回步骤 2。 […]

回复

回复 Remmina 取消回复

Avatar placeholder

您的邮箱地址不会被公开。 必填项已用 * 标注