网络流总结-网络的最大流

邻接表中的边数 int s[MAXN]; //dfs中保存节点的栈 int pre[MAXN]; int rec[MAXN]; int mins[MAXN]; int head[MAXN]; inline int dfs() //dfs寻找增广路 { int top=1; memset(pre,-1,sizeof(pre)); s[top]=S; pre[S]=S; mins[S]=INF; while(top) { int v=s[top--]; for(int i=head[v];i!=-1;i=edge[i].next) { int u=edge[i].to; if(pre[u]==-1 && edge[i].flow>0) { pre[u]=v; rec[u]=i; mins[u]=min(mins[v],edge[i].flow); s[++top]=u; } } if(pre[T]!=-1) //直到找到了汇点T return mins[T];//每次返回增广路径中,容量最小的值 } return -1; // 不存在增广路径 } int Ford_Fulkerson() { int add,Maxflow=0; while((add=dfs())!=-1) //算法直到无法找到增广路径时才停止 { Maxflow+=add; for(int i=T;i!=S;i=pre[i]) //修改残留网络 { edge[rec[i]].flow-=add; //正向减去流量 edge[rec[i]^1].flow+=add;//反向增加流量 } } return Maxflow; } 这是Edmonds-Karp算法代码的实现,bfs使得找到的增广路节点数最少,和上面dfs版本代码的唯一不同就是把保存节点的栈改成了队列, struct Node { int to; int flow; int next; }edge[MAXN*MAXN]; int n,m; //顶点数,边数 int S,T; //源点,汇点 int tot; //邻接表中的边数 int q[MAXN]; //BFS中保存节点的队列 int pre[MAXN]; int rec[MAXN]; int mins[MAXN]; int head[MAXN]; inline int bfs() //bfs寻找增广路 { int h,t; h=t=0; memset(pre,-1,sizeof(pre)); q[h]=S; pre[S]=S; mins[S]=INF; while(h<=t) { int v=q[h++]; for(int i=head[v];i!=-1;i=edge[i].next) { int u=edge[i].to; if(pre[u]==-1 && edge[i].flow>0) { pre[u]=v; rec[u]=i; mins[u]=min(mins[v],edge[i].flow); q[++t]=u; } } if(pre[T]!=-1) //直到找到了汇点T return mins[T];//每次返回增广路径中,容量最小的值 } return -1; // 不存在增广路径 } int Edmonds_Karp() { int add,Maxflow=0; while((add=bfs())!=-1) //算法直到无法找到增广路径时才停止 { Maxflow+=add; for(int i=T;i!=S;i=pre[i]) //修改残留网络 { edge[rec[i]].flow-=add; //正向减去流量 edge[rec[i]^1].flow+=add;//反向增加流量 } } return Maxflow; } 在算法结束时候,还顺带产生了一个副产品,最小割。 什么是最小割, 观察下图,联想前面的算法,很容易发现,无法找到增广路径等价于从S出发已经无法到达T的。换句话说,此时S和T已经被截断了。而这种将图中的点分割为两个不相交点集的情况也就是网络的割集,简称割。 网络的割[S,T] —— 将点集V划分为S和T两部分,(其中源s属于S且汇t属于T),而从S指向T的边组成割。,图1-5便展示了一个割， ? 割容量 —— 割中所有边的容量和 ? 最小割 —— 容量最小的割 ? 最大流最小割定理 网络的最大流值,该网络的最小割容量 1 2 S T 3 4 图,1-5 下面我来简单证明一下最大流最小割定理, 首先当网络达到最大流的时候,S和T已经被截断,既网络已经形成了割,那么只需要证明这个割的割容量是所有割里最小的就可以。 显然,最小割不会有多余的割边。例如在图1-5中,路径,S , 1 , 2 , T，,只有一个割边,S , 1，，但在路径,S , 1 , 3 , 4 , T，中,存在三个割边,S , 1，,,1 , 3，,,4 , T，。显然,割边,4 , T，是多余的割边,因此图1-5中的割必然不是最小割,因为去掉,1,3，这个割边便能得到割容量更小的割。 因为最小割没有多余的割边,所以所有的割边都是必要的,由此得到了最小割的一个性质,去掉任意一个割边,S和T便能够连通。 所以,若有某一个流量从S出发,若想到达T,必定要经过最小割中的某一割边,且只会经过这一个割边,因为没有多余的割边，。当然每个割边都有对应的容量限制,由于是最小割,所以,每个割边一定会选取路径中容量最小的边当成最小割的割边,然后由木桶效应和最大流数值上的唯一性可知不难想到,当网络达到最大流时,其流量 的值必然等于这些割边的容量之和,所以最大流等于最小割。 至此,网络流的基础知识,已经阐述完毕。而就算是最简单的最大流问题,其难度不是求最大流的具体算法,而在于如何能够根据题意巧妙的构建图网络,把现实的问题抽象为求最大流的问题,而下面的内容也将针对这些建图的技巧展开。 注,对于后文中所举到的所有例子,一定先自己去尝试而后再阅读文中的解答,才能有最大的乐趣和收获。 第二部分,构图技巧 所谓的构图,其实就是说把实际的问题抽象成网络图形的一种技巧。因为问题的千变万化而导致出构图的千变万化,使得网络流问题往往具有较好的隐藏性,或者说把问题抽象成网络图形较困难，。但正是因为网络流很高的灵活性,使得解决网络流问题拥有了很大的乐趣。 普通构图, 面对具体问题时,将问题转换成熟悉的模型,进而求解的思维,正是网络流构图技巧的基本要领。 以PKU 1698 Alice’s Chance为例, , Alice需要接拍n部电影,每部电影有两个限制条件,一,只 有在若干指定的日期才能拍摄这部电影，二,每部电影都有必 须完成的时限。 , Alice每天只能替一个电影小组工作。 问Alice是否能完成这n部电影的拍摄。 第一步,判断题目是否可能是最大流问题, 但凡是最大流问题,几乎都会涉及到最值问题,所以如果题目可以抽象成求某最大值或者最小值问题,就可以去尝试构建网络模型。 注意题目其实是在问Alice最多能拍几部电影,只是求得最大值后,还需要判断最大值是否等于n。 但注意到电影并不是一次性拍完的,而是在累加工作次数,达到要求才算是完成该部电影。所以问题就变成了如何安排Alice每天的工作,使得每部电影都能达到对应的需求。咋一看,似乎问题并没有最值问题,但仔细思考后,便不难理出其中的关系,工作的安排—>每部电影的工作量—>电影的完成数目。所以,此题属于最值问题。,?—>‘表示直接影响关系， 第二步,根据题意和样例,尝试构造网络模型。 关于最值问题的题目很多,但只有一小部分是适合采用最大流解决的,所以解题的核心,就是如何构图以便符合题目的条件限制。 网络图的特殊性在于它具有源汇点,所以一般习惯是从源点和汇点着手。源点是源泉,可以想象成是付出,在此题中Alice拥有的就是每天的时间,所以她付出的也就是时间,当然由于每天只能完成一部电影的某些工作,所以从源点出发的边,其容量都为1， 1 (1) 2 (1) 3 S T (1) 4 (1) 5 (1) (1) 6 7 汇点是聚集,可以想象成是收获,在此题中Alice收获的是每部电影的工作积累量,工作天数，。为了得到一个最优的工作安排,显然不需要浪费工作时间在已经完成的电影上,如何在图中体现这一限制,就是每部电影流向汇点的边容量为该电影需要的工作天数。而 且,这样连边的效果,使得问题得到了极大的简化,能否完成A,B,C三部电影等价于,汇点T能否接收到4+6+5=15天的工作日。 1 2 A (4) 3 (6) S B T 4 (5) 5 C 6 7 那么,具体到某一天,它的应该和谁连通,相当于这天的工作安排可以给哪部电影，,因为我们并没有具体的方案安排,所以对于能在第i天工作的电影j,就连一条容量为1的边(i,j)。 1 2 A (4) 3 (6) S B T 4 (5) 5 C 6 7 上图表示对于第一周的7天,周一可以安排给电影A,周二可以安排给电影B或电影C,周六可以安排给电影B,周日可以安排给电影B。 至此,题目给出的条件已经利用完毕。 第三步,验证构图的正确性,并解答之。 好的构图思路往往是经过反复的推敲,巧妙的利用题目条件得到的,所以经常需要验证构图的正确性和计算效率。 图中的容量约束条件一一对应,首先,每天Alice都有一次工作 的机会,她可以选择当天到哪部电影剧组工作,当然前提是符合条件约束，。其次,如果某个电影接受了某一次的工作,那么该电影流向汇点的流量,该电影的工作天数，增加1,当然为了不造成浪费,每部电影的总流量又被其需求量限制,相当于当某个电影达到了需求后,便把机会让给了其他电影，。所以如果对上图实施最大流算法,若得到的最大流等于所有电影的工作需求之和,则Alice能够完成这所有电影的拍摄,否则不能完成所有的拍摄。很直观的解答,当最大流等于所有电影的工作需求之和时,图中红线部分的流量一定都达到了上限,既所有电影一定恰好达到了其工作日的需要。而当最大流不等于所有电影的工作需求之和时,一定是因为不管如何的安排,图中红线部分都不能被全部填满,否则最大流便可以增加,显然矛盾，,即一定有某些电影不能拍摄完成。 再来看看时间效率,点总数为50*7+20+2=372。边总数为350*50=17500。用普通的EK算法也能够解决。 判断问题的范畴,然后将题目条件一一罗列出,进而将实际问题抽象成网络图,最后用最大流算法解决问题,正是最大流问题的一般解题思路。而利用条件将实体抽象的基本思维转换,正是由感性认识到理性感知的必备素养。 技巧构图 进一步的,有了一般的构图思维后,便可以尝试一些比较有技巧的构图。以PKU 1149 PIGS为例, , 有 M 个猪圈,M ? 1000，,每个猪圈里初始时有若干头猪。 , 一开始所有猪圈都是关闭的。 , 依次来了 N 个顾客,N ? 100，,每个顾客分别会打开指定 的几个猪圈,从中买若干头猪。 , 每个顾客分别都有他能够买的数量的上限。 , 每个顾客走后,他打开的那些猪圈中的猪,都可以被任意地调 换到其它开着的猪圈里,然后所有猪圈重新关上。 问总共最多能卖出多少头猪。 举个例子来说。有 3 个猪圈,初始时分别有 3、 1 和 10 头猪。依次来了 3 个顾客,第一个打开 1 号 和 2 号猪圈,最多买 2 头，第二个打开 1 号 和 3 号猪圈,最多买 3 头，第三个打开 2 号猪圈,最多买 6 头。那么,最好的可能性之一就是第一个顾客从 1 号圈买 2 头,然后把 1 号圈剩下的 1 头放到 2 号圈，第二个顾客从 3 号圈买 3 头，第三个顾客从 2 号圈买 2 头。总共卖出 2 + 3 + 2 = 7 头。 不难想像,这个问题的网络模型可以很直观地构造出来。就拿上 面的例子来说,可以构造出图 2-1 所示的模型,图中凡是没有标数 字的边,容量都是 +?，, , 三个顾客,就有三轮交易,每一轮分别都有 3 个猪圈和 1 个 顾客的节点。 , 从源点到第一轮的各个猪圈各有一条边,容量就是各个猪圈里 的猪的初始数量。 , 从各个顾客到汇点各有一条边,容量就是各个顾客能买的数量 上限。 , 在某一轮中,从该顾客打开的所有猪圈都有一条边连向该顾客, 容量都是 +?。 , 最后一轮除外,从每一轮的 i 号猪圈都有一条边连向下一轮 的 i 号猪圈,容量都是 +?,表示这一轮剩下的猪可以留到下 一轮。 , 最后一轮除外,从每一轮被打开的所有猪圈,到下一轮的同样 这些猪圈,两两之间都要连一条边,表示它们之间可以任意流 通。 图 2-1 很容量验证,这个网络模型的最大流量就是最多能卖出的数量。但图中最多会有 2 + N + M × N ? 100,000 个节点。O(???)o,就算用较高效的Dinic算法和Sap算法也无能为力,后文将会对这两种高效的最大流算法进行详解，。 这个模型虽然很直观,但是节点数太多了,计算速度肯定会很慢。其实不用再想别的构图,就让我们继续上面的例子,用合并的方法来简化这个网络模型。 首先,最后一轮中没有打开的猪圈就可以从图中删掉了,也就是图 2-2 中红色的部分,显然它们对整个网络的流量没有任何影响。 图 2-2 接着,看图 2-2 中蓝色的部分。根据Matrix67总结出的以下几个规律,可以把这 4 个点合并成一个, 规律 1. 如果几个节点的流量的来源完全相同,则可以把它们合并成一个。 规律 2. 如果几个节点的流量的去向完全相同,则可以把它们 合并成一个。 规律 3. 如果从点 u 到点 v 有一条容量为 +? 的边,并且 u 是 v 的唯一流量来源,或者 v 是 u 的唯一流量去向,则可以把 u 和 v 合并成一个节点。 根据规律 1,可以把蓝色部分右边的 1、 2 号节点合并成一个，根据规律 2,可以把蓝色部分左边的 1、 2 号节点合并成一个，最后,根据规律 3,可以把蓝色部分的左边和右边,已经分别合并成了一个节点，合并成一个节点。于是,图 2-2 被简化成了图 2-3 的样子。也就是说,最后一轮除外,每一轮被打开的猪圈和下一轮的同样这些猪圈都可以被合并成一个点。 图 2-3 接着,根据规律 3,图 2-3 中的蓝色节点、2 号猪圈和 1 号顾客这三点可以合并成一个，图 2-3 中的两个 3 号猪圈和 2 号顾客也可以合并成一个点。当然,如果两点之间有多条同向的边,则这些边可以合并成一条,容量相加,这个道理很简单,就不用我多说了。最终,上例中的网络模型被简化成了图 2-4 的样子。 图 2-4 让我们从图 2-4 中重新总结一下构造这个网络模型的规则, , 每个顾客分别用一个节点来表示。 , 对于每个猪圈的第一个顾客,从源点向他连一条边,容量就是 该猪圈里的猪的初始数量。如果从源点到一名顾客有多条边, 则可以把它们合并成一条,容量相加。 , 对于每个猪圈,假设有 n 个顾客打开过它,则对所有整数 i ? [1, n),从该猪圈的第 i 个顾客向第 i + 1 个顾客连 一条边,容量为 +?。 , 从各个顾客到汇点各有一条边,容量是各个顾客能买的数量上 限。 拿我们前面一直在讲的例子来说,1 号猪圈的第一个顾客是 1 号顾客,所以从源点到 1 号顾客有一条容量为 3 的边，1 号猪圈的第二个顾客是 2 号顾客,因此从 1 号顾客到 2 号顾客有一条容量为 +? 的边，2 号猪圈的第一个顾客也是 1 号顾客,所以从源点到 1 号顾客有一条容量为 1 的边,和之前已有的一条边合并起来,容量变成 4，2 号猪圈的第二个顾客是 3 号顾客,因此从 1 号顾客到 3 号顾客有一条容量为 +? 的边，3 号猪圈的第一个顾客是 2 号顾客,所以从源点到 2 号顾客有一条容量为 10 的边。 新的网络模型中最多只有 2 + N = 102 个节点,效率已经得到很大的提高。可以这样理解这个新的网络模型,对于某一个顾客,如果他打开了猪圈 h,则在他走后,他打开的所有猪圈里剩下的猪都有可能被换到 h 中,因而这些猪都有可能被 h 的下一个顾客买走。所以对于一个顾客打开的所有猪圈,从该顾客到各猪圈的下一个顾客,都要连一条容量为 +? 的边。 在面对网络流问题时,如果一时想不出很好的构图方法,不如先构造一个最直观,或者说最“硬来”的模型,然后再用合并节点和边的方法来简直化这个模型。经过简化以后,好的构图思路自然就会涌现出来了。这是解决网络流问题的一个好方法。 而这里所列出的三条规律,完全没有必要进行死记硬背,只要在化简网络图时,记住等价和简化这两个概念,对于大部分的图化简,便都能够手到擒来。 当然对于其他更多的精致构图,往往是在灵机一动时,被顺利的“秒杀”。但我想,对于大部分人而言,循序渐进,由浅入深的这种学习和思维方式,往往更能达到事半功倍的效果。等到脑海中沉淀的知识多了,见识的各类模型多了,快速巧妙的构图,也便离你不远了。 对于最大流问题的解决,有着许多种算法来实现,下面将针对一些高效和常见的算法进行一次总结。 第三部分,最大流算法总结, 一:增广路算法 在残余网络中不断的找增广路 1. Ford-Fulkerson 2这是一个用dfs找任意增广路的算法.时间复杂度是O(VE), 时间效率偏低。 2. Edmonds-Karp 2用bfs代替了dfs寻找增广路,时间复杂度是O(VE),时间 效率偏低。 3. Dinic 预处理出层次图,然后在层次图上进行增广,时间复杂度是 2O(VE),实际应用中时间效率较好。 4. Shortest Augmenting Paths(也就是很流行的SAP算法) 故名思议,就是找最短的增广路,把EK算法的O(E)时间优化 2到了O(V),故复杂度为O(VE) 不过加了间隙优化后效率和Dinic不可同日而语 ,时间效率 非常好。 二:预留推进算法 非常形象的灌水机制,一开始源点在最高,向各个管道灌水,如果一个点有盈余,那么它必需往低处流(Push),不能留的话上升高度(Relabel)后再往低处流 1. Push_Relabel 4很朴实的预留推进算法,O(V) 2. Relabel_to_Front 用一个List维护各个点,当一个点被relabel后回到List 3(to front)再往后计算,O(V) 首部 3. Highest_Relabel(传说中的HLPP算法,高标预流推进 21/2–Highest_Label_Preflow_PushO(VE)) Relabel_to_Front的改进版,List分层从最高的点开始流, 加上BFS预处理和间隙优化后效率会有不可思议的提高 一,增广路算法。 增广路的算法很多,其中Ford-Fulkerson方法是基础,也是重点,因为其它的算法都只是在优化它。在这里我只提目前公认效率最高的两种算法,Dinic与Sap。两种算法的核心优化思想都是在 优化寻找增广路的效率,以达到加速的目的。 务必记住,增广路算法求最大流的本质,就是不停的寻找增广路径。直到找不到增广路径为止。 Dinic: Dinic算法实质是Edmonds-Karp算法的改进。回想下,在Edmonds-Karp算法中,每次利用BFS找出最短,经过的节点数最少，的增广路,然后进行增广,并修改残留网络。 如何改进, 假如我们能预知哪些路径不是最短的,那么每次寻找增广路的时候不就一定能走最短的那些吗, 如何预知, 当然就是预处理,在寻找增广路之前,我们可以从源点出发,做一次BFS,那么很容易就计算出了每个顶点到源点的距离,经过的节点数，。所以层次图就相当于是一个已经预处理好的增广路标志图。然后在层次图的基础上进行增广,直到无法找到增广路。然后在新的残留网络下重新计算出层次图,继续增广,直到某次计算层次图时,源点已经无法到达汇点,算法结束,此时便已找到了最大流。 在进一步介绍dinic算法的具体实现和优化前,必须先理解几个名词, 1顶点的层次 uu在残留网络中,我们把从源点到点的最短路径长度称作点的层 level(u)次,记为。源点的层次为0。在下面这张残留网络中, 1 汇点 源点 2 0 3 3 每个点旁边的数字即表示该点在图中的层次。 2层次图的概念 G,(V,E)G,(V,E)333222,对于剩余图中的一 我们这样定义层次图 (u,v),E(u,v)level(u)，1,level(v)3条边,当且仅当时,边，V,{u|E中有边与u相连}33 直观地讲,层次图是建立在剩余图,残留网络，基础之上的一张“最短路图”。从源点开始,在层次图中沿着边不管怎么走,经过的路径一定是终点在剩余图中的最短路。 3阻塞流的概念 Gf3在流量网络中存在一可行流,当该网络的层次图中不存在增 Gf3广路时,我们称流函数为层次图的阻塞流。 4阻塞点的概念 当从残留网络中节点i出发,无法到达i的下一层次的节点时,已经不可能存在经过i的最短增广路了,即i已经被阻塞了,此时称节点i为阻塞点。显然寻路过程中寻找的节点必须是非阻塞点。 Dinic 算法流程如下, 1) 计算残留网络的层次图。我们定义 dis 为顶点 i 距离源 S 所经过到最少节点数,求出所有顶点的 dis 值,dis[] 值 相同的顶点属于同一层,这就是网络的层次图。 2) 在层次图上进行 BFS(或用DFS) 增广,直到不存在增广路 径。这时求得的增广路径上顶点是分层的,路径上不可能存在两 个顶点属于同一层,即 dis[i]== dis[j] (i ? j )。同时, 求得层次图后,我们可以在层次图上进行多次增广。 3) 重复 1 和 2。直到层次图中源点已经无法到达汇点,即已 不存在增广路。 优化, 多路增广:注意到,每次BFS(或DFS)完成后,会找到路径中容 量最小的一条边。在这条边之前的路径的容量是大于等于这条边 的容量的。那么从这条边之前的点,可能引发出别的增广路径。 比如说 S -> b -> c -> d -> T 是一条增广路径,容量最 小的边是 b -> c。 可能存在一条 S -> b -> e -> f -> g -> T 这样的增广路 径。 这样的话,在找到第一条增广路径后,只需要回溯到 b 点,就可 以继续找下去了。 这样做的好处是,避免了找到一条路径就从头开始寻找另外一条 的开销。也就是再次从 S 寻找到 b 的开销。 同时,在同一次的BFS( 或DFS) 中。如果判断出一个点是阻塞 点,就将这个点在层次图中抹去。 至此,Dinic算法有了较完美的实现, 静态邻接表实现代码, #define MAXN 40002 #define INF 100000000 struct Node { int to; int flow; int next; }edge[MAXN*8]; int n,m; int S,T; int tot; int q[MAXN]; int dis[MAXN]; //记录层次 int pre[MAXN]; int rec[MAXN]; int head[MAXN]; bool block[MAXN]; //标记阻塞 inline void add_edge(int a,int b,int flow) //添边 { edge[tot].to=b; edge[tot].flow=flow; edge[tot].next=head[a]; head[a]=tot++; edge[tot].to=a; edge[tot].flow=0; edge[tot].next=head[b]; head[b]=tot++; } void init() { int i; int h=0,t=0; for(i=0;i<=T;i++) dis[i]=INF; q[h]=S; dis[S]=0; while(h<=t) { int u=q[h++]; for(i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; if(dis[v]==INF && edge[i].flow) { dis[v]=dis[u]+1; q[++t]=v; } } } } int dinic() { int i,j; int top=S,MaxFlow=0,mins=INF; pre[S]=S; init(); memset(block,0,sizeof(block)); while(dis[T]!=INF) { for(i=head[top];i!=-1;i=edge[i].next) { if(edge[i].flow && dis[top]+1==dis[edge[i].to] && !block[edge[i].to]) { break; } } if(i!=-1) //找到下一个节点 { j=edge[i].to; mins=min(mins,edge[i].flow); pre[j]=top; rec[j]=i; top=j; if(top==T) { i=-1; MaxFlow+=mins; for(;top!=S;top=pre[top]) { edge[rec[top]].flow-=mins; edge[rec[top]^1].flow+=mins; if(!edge[rec[top]].flow) //记录最早出现的"瓶 "边 颈 i=top; } if(i!=-1) { i=pre[i]; mins=INF; for(j=i;j!=S;j=pre[j]) { mins=min(mins,edge[rec[j]].flow); } top=i; //多路增广,而不是重新从S开始找。 } } } else { block[top]=true; //标记阻塞 top=pre[top]; //回溯 if(block[S]) { init(); memset(block,0,sizeof(block)); } } } return MaxFlow; } SAP, 算法的优化是无尽头的,Dinic 算法要多次计算层次图,增加了复杂度。是不是可以不多次计算层次图呢,答案是肯定,由此产生了 SAP 算法。 SAP 计算的是反向图的层次图,即计算出的是离汇点的距 离，,这和原图的层次图是作用是一样的,当然其实Dinic也可以计算反向图的层次图,确保增广路径最短。SAP 意思就是 Shortest Augmenting Paths,最短增广路径。计算反向图的层次图的目的是便于重新给顶点标号,即重新确定其层次图。 具体做法为,当我们找到一条经过顶点 i 的增广路径后,对于所有边,计算出 m= min{ h[j] } ,这是我们就可以把 i 重新标号为 h= m+ 1。当然,实际上,我们可以不需要预处理计算反向图的层次图,而是把所有顶点的层次标为0,当点边数目不大时,这对效率没多大影响。但如果点边数非常大,效率则会大打折扣,所以一般还是选择计算层次图。然则这样优化后还不够,又出现了一个 gap ,间隙，优化。所谓 gap 优化就是计算出层次图后,层次出现断层,这是可以确定残余网络中不存在增广路径了,算法就可以提前结束。这个优化看似微小,实际作用却很大。做法就是保存某一个标号在残余网络中出现的次数,如果次数是 0 ,则表示层次断层了。 同样的,在具体介绍SAP算法的实现和优化前,需要理解几个名词: 1距离标号的概念 对于每个顶点u 赋予一个非负整数值d(u)来描述u 到t 的―距 离‖ 远近,称它为距离标号,即到汇点距离的下界,并且满足以下两个条件, ,1，d(t) =0。 ,2，对于残留网络f G 中的一条弧(u,v),d(u) d(v) + 1。 在下面这张残留网络中, 2 源点 1 汇点 3 0 2 每个点旁边的数字即表示该点在图中的距离标号。 2允许弧的概念 如果残留网络f G 中的一条弧(u,v)满足d(u) =d(v) + 1,我们称(u,v)是允许弧,由允许弧组成的一条s-t 路径是允许路。显然,允许路是残留网络f G 中的一条最短增广路。 3修改距离标号的概念 当找不到允许路的时候,我们需要修改某些点的d 值。实现中我们用一个DFS ,为了提高效率,通常也用非递归的迭代法来实现， 实现这个寻找最短增广的过程,如果无法继续向前,那么我们就修改当前结点的距离标号为,min,d[相邻边]，+1。 SAP算法的实现流程, Step0,置初始可行流x为零流，计算精确的距离函数d，令当 前节点i,s。 Step1,若d,s，0}时,令 d(i),min{d(j)，1，ijA(x)且u(x)>0},否则令 d(i),n，且当i?s时再令i,pre(j)。转Step1。 注,A(x)为残留网络,u(x)为剩余容量 优化, SAP 算法有两个重要的优化,Gap,间隙， 优化和当前弧优化。 Gap优化,我们可以注意到由于残留网络的修改只会使d(u)越来越大,因为修改前d(u) < d(v) + 1,而修改后会存在d(u) =d(v) +1,因此d(u)变大了，,所以说d 函数是单调递增的,这就提示我们,如果d 函数出现了―断层‖,即没有d(u) =k,而有d(v) =k 1,这时候必定无法再找到增广路径。 我们可以这么想,在某次修改d(u)后第一次出现了断层k,显然d(u)原来是等于k的,且修改后d(u)>k,又d(u)需要修改的原因是因为修改前d(u) < d(v) + 1,,所以d(v)>k-1,因为k出现了断层,所以d(v)?k,故有d(v)>k。 而d函数是单调递增的,所以k 这个空缺便永远不会被补上。因为找出的增广路径s-u-….-v-t必定符合d[s]+m=d[u]+m-1=….=d[v]+1=d[t] (其中m为增广路径中节点的个数),所以如果中间有不可弥补的断层,一定无法再找到增广路径了。 所以我们加一个gap 数组,统计一下d 函数的每个值各有多少个,如果某次修改后出现了gap[k]=0,则说明出现了―断层‖,可以直接结束算法。 当前弧优化,可以注意到一个事实,如果说在某次迭代中从i 出发的弧(u,v)不是允许弧,则在顶点i 的标号修改之前(u,v)都不可能是允许弧。,因为d(u)不变,d(v)单调不降且d(u)dis[edge[i].to]) { mindis=dis[edge[i].to]; } } gap[dis[u]=mindis+1]++; u=pre[u]; } } return Maxflow; } 好的算法往往不仅具有较高的时间效率,而且有着较短的代码实现 和容易理解的算法过程。Dinic和Sap正是因为有了这些特点,才 成了解决最大流问题的真正利器。而加了两种优化得Sap,时间效率更是高的惊人,已经成为最大流算法中的主力。 至于几种预留推进的算法,由于其实现原理不再是增广路,而是采用了压入(push)和重标记(relabel)法,且代码实现较繁琐,所以这里就不进行具体的叙述。 附效率测试与比较(测试数据均为点数10000的稠密图), 算法 高标推进 SAP(GAP) Dinic SAP(NO GAP) EK 时间(s) 5.67 6.02 11.35 23.90 55.77 第四部分,费用流 流最重要的应用是尽可能多的分流物资,这也就是我们已经研究 过的最大流问题。然而实际生活中,最大配置方案有时不止一种, 一旦有了选择的余地,费用的因素就自然参与到决策中来。 V1 (6,3) (5,4) S T (3,7) (8,2) V2 费用流问题 图 3-1 图3-1是一个最简单的例子,弧上标的两个数字第一个是容量, 第二个是费用。这里的费用是单位流量的花费,譬如fs1=4,所 需花费为3*4=12。 容易看出,此图的最大流为8,等于fs1 = f1t = 5 加上 fs2 = f2t = 3 。所以它的费用是,3*5+4*5+7*3+2*3 = 62。 然后要理清楚几个概念, 1费用流的定义 设有带费用的网络流图G = (V, E, C, W),每条弧 对应三个非负整数Cij、Wij、fij,表示该弧的容量,费用和当 前流量。若流f满足, 1. 流量V(f)最大。 2. 满足1的前提下,流的费用Cost(f) =??E (fij * Wij)最小。 就称f是网络流图G的最小费用最大流。 1.流量V(f)最大。 2.满足1的前提下,流的费用Cost(f) =??E (fij * Wij)最大。 就称f是网络流图G的最大费用最大流。 2最小费用可改进路 设P是流f的可改进路,定义??P(Wij*fij) 为P 的费用 如果P是关于f的可改进路中费用最小的,就称P是f的最 小费用可改进路。 3求费用流的基本思想 求最小费用最大流的基本思想是贪心法。即,对于流f,每次选择 最小费用可改进路进行改进,直到不存在可改进路为止。这样的 得到的最大流必然是费用最小的。 综合以上几个概念和思想,我们有了求费用流的一般思路,不断寻找最小费用可改进路,直到不存在可改进路为止。 那么,如何寻找最小费用可改进路, 首先需要用到残留网络,只是除了残留容量之外,还需要给每条边加上它的费用, 设带费用的网络流图G = (V, E, C, W),它的一个可行流是f。 我们构造带权有向图B = (V‘, E‘),其中, V‘ = V。 若?E,fij?E‘,权为 Wij。 若?E,fij>0,那么?E‘,权为-Wij。 显然,B中从S到T的每一条道路都对应关于f的一条可改进 路，反之,关于f的每条可改进路也能对应B中从S到T的一条 路径。即两者存在一一映射的逻辑关系。 故若B中不存在从S到T的路径,则f必然没有可改进路，否 则,B中从S到T的最短路径即为f的最小费用可改进路。 所以,现在的问题变成,给定带权有向图B = (V‘, E‘),求 从S到T的一条最短路径。 对于新的残留网络带权图B,反向边中的费用之所以是-Wij, 正是因为如果在后面的决策中,决定减少正向边的流量,相当于 反向边增加流量,则显然费用也应该做相应的改变,故反向边中 的费用是-Wij。 想必对于求带权图的最短路径,大家已然不陌生。但考虑到图中可能存在权值为负数的弧,故一般不能采用Dijkstra算法，Floyd-Warshall或Bellman-Ford算法的效率又不尽如人意——所以我们不妨采用效率较高的Spfa算法。 至此,我们得到了求费用流的一般算法,并且是在用Ford-Fulkerson迭代法求得最大流前提下的再求出最小费用的,而spfa的原理也是迭代松弛,因此这种求费用流的算法一般称之为Ford-Fulkerson迭代法。 那么,Ford-Fulkerson迭代法应该如何实现呢,其实一点都不复杂,只需要在处理边时,增加费用这一权值,然后把Ford-Fulkerson中寻找增广路的bfs部分改成spfa寻找增广路,然后再增加流量时候,同时增加费用即可。,当然有时候,并不需要求得最大流,所以根据题意可以自行选择是否记录最大流， 实现代码, //若要求最大费用最大流,只需将spfa改成求最长路即可 #define MAXN 1002 #define MAXM 40002 #define INF 100000000 struct Node { int to; int cost; //费用 int flow; //剩余容量 int next; }edge[MAXM]; int n,m; int tot; int S,T; int q[MAXM]; int dis[MAXN]; int pre[MAXN]; int rec[MAXN]; int head[MAXN]; bool vis[MAXN]; void add_edge(int a,int b,int cost,int flow) { edge[tot].to=b; edge[tot].cost=cost; edge[tot].flow=flow; edge[tot].next=head[a]; head[a]=tot++; edge[tot].to=a; edge[tot].cost=-cost; edge[tot].flow=0; edge[tot].next=head[b]; head[b]=tot++; } bool spfa() //spfa寻找当前最小费用增广路 { int i; int h,t; for(i=0;i<=T;i++) { dis[i]=INF; vis[i]=false; } h=t=0; q[h]=S; dis[S]=0; vis[S]=true; while(h<=t) { int v=q[h++]; vis[v]=false; for(i=head[v];i!=-1;i=edge[i].next) { int u=edge[i].to; if(dis[u]>dis[v]+edge[i].cost && edge[i].flow>0) { dis[u]=dis[v]+edge[i].cost; pre[u]=v; rec[u]=i; if(!vis[u]) { q[++t]=u; vis[u]=true; } } } } if(dis[T]==INF) //已不存在增广路 return false; else return true; } int mincostmaxflow() { int mincost=0; while(spfa()) { int i; int minflow=INF; for(i=T;i!=S;i=pre[i]) { if(edge[rec[i]].flow论文

政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载