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;//返回没找到增广路
}

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

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;
}

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;
}

分类: 所有

XZYQvQ

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

1 条评论

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

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *