最大流模板【EdmondsKarp算法,简称EK算法,O(m^2n)】

2024-08-29 05:32

本文主要是介绍最大流模板【EdmondsKarp算法,简称EK算法,O(m^2n)】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

转自http://blog.sina.com.cn/s/blog_6cf509db0100uy5n.html,好东西大家一起分享

因为是初学教程,所以我会尽量避免繁杂的数学公式和证明。也尽量给出了较为完整的代码。
本文的目标群体是网络流的初学者,尤其是看了各种NB的教程也没看懂怎么求最大流的小盆友们。本文的目的是,解释基本的网络流模型,最基础的最大流求法,即bfs找增广路法,也就是EK法,全名是Edmond-Karp,其实我倒是觉得记一下算法的全名和来历可以不时的拿出来装一装。
    比如说这个,EK算法首先由俄罗斯科学家Dinic在1970年提出,没错,就是dinic算法的创始人,实际上他提出的也正是dinic算法,在EK的基础上加入了层次优化,这个我们以后再说,1972年Jack Edmonds和Richard Karp发表了没有层次优化的EK算法。但实际上他们是比1790年更早的时候就独立弄出来了。
    你看,研究一下历史也是很有趣的。
    扯远了,首先来看一下基本的网络流最大流模型。
    有n个点,有m条有向边,有一个点很特殊,只出不进,叫做源点,通常规定为1号点。另一个点也很特殊,只进不出,叫做汇点,通常规定为n号点。每条有向边上有两个量,容量和流量,从i到j的容量通常用c[I,j]表示,流量则通常是f[I,j]。通常可以把这些边想象成道路,流量就是这条道路的车流量,容量就是道路可承受的最大的车流量。很显然的,流量<=容量。而对于每个不是源点和汇点的点来说,可以类比的想象成没有存储功能的货物的中转站,所有”进入”他们的流量和等于所有从他本身”出去”的流量。
    把源点比作工厂的话,问题就是求从工厂最大可以发出多少货物,是不至于超过道路的容量限制,也就是,最大流。
    比如这个图。每条边旁边的数字表示它的容量。


下面我们来考虑如何求最大流。
    首先,假如所有边上的流量都没有超过容量(不大于容量),那么就把这一组流量,或者说,这个流,称为一个可行流。一个最简单的例子就是,零流,即所有的流量都是0的流。
我们就从这个零流开始考虑,假如有这么一条路,这条路从源点开始一直一段一段的连到了汇点,并且,这条路上的每一段都满足流量<容量,注意,是严格的<,而不是<=。那么,我们一定能找到这条路上的每一段的(容量-流量)的值当中的最小值delta。我们把这条路上每一段的流量都加上这个delta,一定可以保证这个流依然是可行流,这是显然的。
    这样我们就得到了一个更大的流,他的流量是之前的流量+delta,而这条路就叫做增广路。
    我们不断地从起点开始寻找增广路,每次都对其进行增广,直到源点和汇点不连通,也就是找不到增广路为止。当找不到增广路的时候,当前的流量就是最大流,这个结论非常重要。
寻找增广路的时候我们可以简单的从源点开始做bfs,并不断修改这条路上的delta量,直到找到源点或者找不到增广路。
这里要先补充一点,在程序实现的时候,我们通常只是用一个c数组来记录容量,而不记录流量,当流量+1的时候,我们可以通过容量-1来实现,以方便程序的实现。

Bfs过程的半伪代码:下面另给一个C++版的模板

</pre><pre name="code" class="cpp">int BFS()
{int i,j,k,v,u;memset(pre,-1,sizeof(pre));for(i=1;i<=n;++i)flow[i]=max_int;queue<int>que;pre[start]=0;que.push(start);while(!que.empty()){v=que.front();que.pop();for(i=1;i<=n;++i){u=i;if(u==start||pre[u]!=-1||map[v][u]==0)continue;pre[u]=v;flow[u]=MIN(flow[v],map[v][u]);que.push(u);}}if(flow[end]==max_int)return -1;return flow[end];
}

但事实上并没有这么简单,上面所说的增广路还不完整,比如说下面这个网络流模型


我们第一次找到了1-2-3-4这条增广路,这条路上的delta值显然是1。于是我们修改后得到了下面这个流。(图中的数字是容量)


这时候(1,2)和(3,4)边上的流量都等于容量了,我们再也找不到其他的增广路了,当前的流量是1。
但这个答案明显不是最大流,因为我们可以同时走1-2-4和1-3-4,这样可以得到流量为2的流。
那么我们刚刚的算法问题在哪里呢?问题就在于我们没有给程序一个”后悔”的机会,应该有一个不走(2-3-4)而改走(2-4)的机制。那么如何解决这个问题呢?回溯搜索吗?那么我们的效率就上升到指数级了。
而这个算法神奇的利用了一个叫做反向边的概念来解决这个问题。即每条边(I,j)都有一条反向边(j,i),反向边也同样有它的容量。
我们直接来看它是如何解决的:
 
在第一次找到增广路之后,在把路上每一段的容量减少delta的同时,也把每一段上的反方向的容量增加delta。即在Dec(c[x,y],delta)的同时,inc(c[y,x],delta)
我们来看刚才的例子,在找到1-2-3-4这条增广路之后,把容量修改成如下

最大流模板【EdmondsKarp算法,简称EK算法,O(m^2n)】

这时再找增广路的时候,就会找到1-3-2-4这条可增广量,即delta值为1的可增广路。将这条路增广之后,得到了最大流2。

最大流模板【EdmondsKarp算法,简称EK算法,O(m^2n)】

那么,这么做为什么会是对的呢?我来通俗的解释一下吧。
事实上,当我们第二次的增广路走3-2这条反向边的时候,就相当于把2-3这条正向边已经是用了的流量给”退”了回去,不走2-3这条路,而改走从2点出发的其他的路也就是2-4。(有人问如果这里没有2-4怎么办,这时假如没有2-4这条路的话,最终这条增广路也不会存在,因为他根本不能走到汇点)同时本来在3-4上的流量由1-3-4这条路来”接管”。而最终2-3这条路正向流量1,反向流量1,等于没有流量。
这就是这个算法的精华部分,利用反向边,使程序有了一个后悔和改正的机会。而这个算法和我刚才给出的代码相比只多了一句话而已。

#include<iostream>
#include<queue>
using namespace std;
const int maxn=205;
const int inf=0x7fffffff;
int r[maxn][maxn]; //残留网络,初始化为原图
bool visit[maxn];
int pre[maxn];
int m,n;
bool bfs(int s,int t)  //寻找一条从s到t的增广路,若找到返回true
{int p;queue<int > q;memset(pre,-1,sizeof(pre));memset(visit,false,sizeof(visit));pre[s]=s;visit[s]=true;q.push(s);while(!q.empty()){p=q.front();q.pop();for(int i=1;i<=n;i++){if(r[p][i]>0&&!visit[i]){pre[i]=p;visit[i]=true;if(i==t) return true;q.push(i);}}}return false;
}
int EdmondsKarp(int s,int t)
{int flow=0,d,i;while(bfs(s,t)){d=inf;for(i=t;i!=s;i=pre[i])d=d<r[pre[i]][i]? d:r[pre[i]][i];for(i=t;i!=s;i=pre[i]){r[pre[i]][i]-=d;r[i][pre[i]]+=d;}flow+=d;}return flow;
}int main()
{while(scanf("%d%d",&m,&n)!=EOF){int u,v,w;memset(r,0,sizeof(r));///for(int i=0;i<m;i++){scanf("%d%d%d",&u,&v,&w);r[u][v]+=w;}printf("%d\n",EdmondsKarp(1,n));}return 0;
}



这篇关于最大流模板【EdmondsKarp算法,简称EK算法,O(m^2n)】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1116979

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

C++中函数模板与类模板的简单使用及区别介绍

《C++中函数模板与类模板的简单使用及区别介绍》这篇文章介绍了C++中的模板机制,包括函数模板和类模板的概念、语法和实际应用,函数模板通过类型参数实现泛型操作,而类模板允许创建可处理多种数据类型的类,... 目录一、函数模板定义语法真实示例二、类模板三、关键区别四、注意事项 ‌在C++中,模板是实现泛型编程

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

基于Java实现模板填充Word

《基于Java实现模板填充Word》这篇文章主要为大家详细介绍了如何用Java实现按产品经理提供的Word模板填充数据,并以word或pdf形式导出,有需要的小伙伴可以参考一下... Java实现按模板填充wor编程d本文讲解的需求是:我们需要把数据库中的某些数据按照 产品经理提供的 word模板,把数据

如何提高Redis服务器的最大打开文件数限制

《如何提高Redis服务器的最大打开文件数限制》文章讨论了如何提高Redis服务器的最大打开文件数限制,以支持高并发服务,本文给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录如何提高Redis服务器的最大打开文件数限制问题诊断解决步骤1. 修改系统级别的限制2. 为Redis进程特别设置限制

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系