网络流算法专题

⽹络流算法2018-03-13 19:02:13在图论中，⽹络流（英语：Network flow）是指在⼀个每条边都有容量（capacity）的有向图分配流，使⼀条边的流量不会超过它的容量。

通常在运筹学中，有向图称为⽹络。

顶点称为节点（node）⽽边称为弧（arc）。

⼀道流必须匹配⼀个结点的进出的流量相同的限制，除⾮这是⼀个源点（source）──有较多向外的流，或是⼀个汇点（sink）──有较多向内的流。

⼀个⽹络可以⽤来模拟道路系统的交通量、管中的液体、电路中的电流或类似⼀些东西在⼀个结点的⽹络中游动的任何事物。

⼀、最⼤流最⼩割定理最⼤流最⼩割定理提供了对于⼀个⽹络流，从源点到⽬标点的最⼤的流量等于最⼩割的每⼀条边的和。

这个定理说明，当⽹络达到最⼤流时，会有⼀个割集，这个割集中的所有边都达到饱和状态。

这等价于在⽹络中再也找不到⼀个从s到t的增⼴路径。

因为只要能找到⼀条增⼴路径，这条增⼴路径肯定要经过最⼩割集中的⼀条边，否则这个割集就不能称之为割集了。

既然这个割集中所有的边都饱和了，因此也就不会存在这样的增⼴路径了。

这个定理的意义在于给我们指明了⽅向：任何算法，只要最后能达到“再也找不到⼀条增⼴路径”，就可以说明这个算法最后达到了最⼤流。

⼆、最⼤流问题在优化理论中,最⼤流问题涉及到在⼀个单源点、单汇点的⽹络流中找到⼀条最⼤的流。

最⼤流问题可以被看作是⼀个更复杂的⽹络流问题（如循环问题（circulation problem））的特殊情况,。

s-t流（从源点s到汇点t）的最⼤值等于s-t割的最⼩容量，这被称为最⼤流最⼩割定理。

下⾯举例来说明这个问题：问题描述：给定⼀个有向图G=(V,E)，把图中的边看作管道，每条边上有⼀个权值，表⽰该管道的流量上限。

给定源点s和汇点t，现在假设在s处有⼀个⽔源，t处有⼀个蓄⽔池，问从s到t的最⼤⽔流量是多少。

这个问题有如下的⼀些限制：容量限制：也就是在每条通路上的流量都不能超过其capacity。

最大流算法研究FordFulkerson和EdmondsKarp算法最大流算法是图论中一个重要的概念和研究领域，它用于解决网络流问题。

在最大流问题中，我们需要找到从源节点到汇节点的最大流量，以便在网络中实现最优的数据传输。

本文将研究两种经典的最大流算法：FordFulkerson算法和EdmondsKarp算法。

1. FordFulkerson算法FordFulkerson算法是由L.R.Ford Jr.和D.R.Fulkerson于1956年提出的经典算法。

该算法基于贪心思想，通过不断寻找增广路径来逐步增加流量，直到达到最大流。

算法步骤如下：1.1 初始化网络中的流量为0。

1.2 找到一条从源节点到汇节点的增广路径。

1.3 计算增广路径上的最小容量。

1.4 将最小容量加到网络中的流量上，并更新相关边的残余容量。

1.5 重复步骤2和步骤3，直到无法找到增广路径。

FordFulkerson算法的核心思想是不断寻找增广路径，并在每次找到增广路径时增加流量，直到无法找到增广路径为止。

该算法的时间复杂度取决于增广路径的数量和最大容量的大小，最坏情况下可以达到O(E|f*|)，其中E是网络中的边数，|f*|是最大流的大小。

2. EdmondsKarp算法EdmondsKarp算法是FordFulkerson算法的一个改进版本，由J.Edmonds和R.Karp于1972年提出。

该算法利用广度优先搜索来寻找增广路径，从而减少了搜索路径的数量，提高了算法的效率。

算法步骤如下：2.1 初始化网络中的流量为0。

2.2 使用广度优先搜索来寻找从源节点到汇节点的最短增广路径。

2.3 计算增广路径上的最小容量。

2.4 将最小容量加到网络中的流量上，并更新相关边的残余容量。

2.5 重复步骤2和步骤3，直到无法找到增广路径。

EdmondsKarp算法的核心思想是利用广度优先搜索来寻找增广路径，从而减少搜索路径的数量，提高算法的效率。

网络流：最小费用最大流（最简单的算法）最小费用流在OI 竞赛中应当算是比较偏门的内容，但是NOI2008 中employee 的突然出现确实让许多人包括zkw 自己措手不及。

可怜的zkw 当时想出了最小费用流模型，可是他从来没有实现过，所以不敢写，此题0 分。

zkw 现在对费用流的心得是：虽然理论上难，但是写一个能AC 题的费用流还算简单。

先贴一个我写的employee 程序：只有不到70 行，费用流比最大流还好写～程序代码:C++#include <cstdio>#include <cstring>using namespace std;const int maxint=~0U>>1;int n,m,pi[550]={0},cost=0;bool v[550]={0};struct etype{int t,c,u;etype *next,*pair;etype(){}etype(int t_,int c_,int u_,etype* next_):t(t_),c(c_),u(u_),next(next_){}void* operator new(unsigned,void* p){return p;}} *e[550],*eb[550];int aug(int no,int m){if(no==n)return cost+=pi[1]*m,m;v[no]=true;for(etype *&i=e[no];i;i=i->next)if(i->u && !v[i->t] && pi[i->t]+i->c==pi[no])if(int d=aug(i->t,m<i->u?m:i->u))return i->u-=d,i->pair->u+=d,d;return 0;}bool modlabel(){int d=maxint,c;for(int i=1;i<=n;++i)if(v[i])for(etype *j=eb[i];j;j=j->next)if(j->u && !v[j->t])if((c=j->c-pi[i]+pi[j->t])<d)d=c;if(d==maxint)return false;for(int i=1;i<=n;++i)if(v[i])pi[i]+=d,e[i]=eb[i];return true;}int main(){freopen("costflow.in","r",stdin);freopen("costflow.out","w",stdout);scanf("%d %d",&n,&m);etype *Pe=new etype[m+m];while(m--){int s,t,c,u;scanf("%d%d%d%d",&s,&t,&u,&c);e[s]=new(Pe++)etype(t, c,u,e[s]);e[t]=new(Pe++)etype(s,-c,0,e[t]);e[s]->pair=e[t];e[t]->pair=e[s];}memmove(eb,e,sizeof(e));do do memset(v,0,sizeof(v));while(aug(1,maxint));while(modlabel());printf("%d\n",cost);return 0;}程序代码:CB大牛翻译的PASCALvarn,m,i,l,s,t,c,cost,u:longint;v:array[0..600]of boolean;dis:array[0..600]of longint;e_n,e_t,e_c,e_u,e_p,e_x:array[0..250000]of longint;function min(a,b:longint):longint;beginif a>b then exit(b);exit(a);end;procedure addedge(s,t,c,u,k:longint);begininc(l);e_n[l]:=e_n[s];e_n[s]:=l;//下一条边e_t[l]:=t;//边的另一端e_c[l]:=c;//边的费用e_u[l]:=u;//边的容量e_p[l]:=l+k;//对应的边end;procedure build(s,t,c,u:longint);beginaddedge(s,t,c,u,1);addedge(t,s,-c,0,-1);end;function aug(no,m:longint):longint;vari,d:longint;beginif no=n then begininc(cost,m*dis[1]);exit(m);end;v[no]:=true;i:=e_x[no];while i<>0 do beginif (e_u[i]>0)and(not v[e_t[i]])and(dis[e_t[i]]+e_c[i]=dis[no]) then begind:=aug(e_t[i],min(m,e_u[i]));if d>0 then begindec(e_u[i],d);inc(e_u[e_p[i]],d);e_x[no]:=i;exit(d);end;end;i:=e_n[i];end;e_x[no]:=i;exit(0);end;function modlabel:boolean;vard,i,j:longint;begind:=maxlongint;for i:=1 to n do if v[i] then beginj:=e_n[i];while j<>0 do beginif (e_u[j]>0)and(not v[e_t[j]])and(e_c[j]-dis[i]+dis[e_t[j]]<d) then d:=e_c[j]-dis[i]+dis[e_t[j]];j:=e_n[j];end;end;if d=maxlongint then exit(true);for i:=1 to n do if v[i] then beginv[i]:=false;inc(dis[i],d);end;exit(false);end;beginassign(input,'coflow.in');reset(input);assign(output,'coflow.out');rewrite(output);readln(n,m);l:=n;for m:=m downto 1 do beginreadln(s,t,u,c);build(s,t,c,u);end;repeatfor i:=1 to n do e_x[i]:=e_n[i];while aug(1,maxlongint)>0 do fillchar(v,sizeof(v),0);until modlabel;writeln(cost);close(output);end.这里使用的是连续最短路算法。

⽹络流ISAP算法的简单介绍（zz）　这⼏天由于种种原因经常接触到⽹络流的题⽬，这⼀类型的题给⼈的感觉，就是要⾮常使劲的YY才能出来点⽐较正常的模型。

尤其是看了Amber最⼩割应⽤的⽂章，⾥⾯的题⽬思路真是充满了绵绵不绝的YD思想。

然⽽⽐赛中，当你YD到了这⼀层后，您不得不花⽐较多的时间去纠结于⼤量细节的实现，⽽冗长的代码难免会使敲错版后的调试显得异常悲伤，因此⼀些巧妙简短⾼效的⽹络流算法在此时便显得犹为重要了。

本⽂⼒求以最简短的描述，对⽐较流⾏的⽹络流算法作⼀定的总结，并借之向读者强烈推荐⼀种效率与编程复杂度相适应的算法。

众所周知，在⽹络流的世界⾥，存在2类截然不同的求解思想，就是⽐较著名的预流推进与增⼴路，两者都需要反向边的⼩技巧。

其中预流推进的算法思想是以边为单元进⾏推流操作。

具体流程如下:置初始点邻接边满流并⽤⼀次反向bfs对每个结点计算反向距离标号，定义除汇点外存量⼤于出量的结点为活动结点，每次对活动结点按允许边（u->v:d[u]=d[v]+1）进⾏推流操作，直到⽆法推流或者该点存量为0，若u点此时仍为活动结点，则进⾏重标号，使之等于原图中进⾏推操作后的邻接结点的最⼩标号+1，并将u点⼊队。

当队列为空时，算法结束，只有s点和t点存量⾮0，⽹络中各顶点⽆存量，⽆法找到增⼴路继续增⼴，则t点存量为最⼤流。

⽽增⼴路的思想在于每次从源点搜索出⼀条前往汇点的增⼴路，并改变路上的边权，直到⽆法再进⾏增⼴，此时汇点的增⼴量即为最⼤流。

两者最后的理论基础依然是增⼴路定理，⽽在理论复杂度上预流推进要显得⽐较优秀。

其中的HLPP⾼标预流推进的理论复杂度已经达到了另⼈发指的O（sqrt(m)*n*n），但是其编程复杂度也是同样的令⼈发指- - 于是我们能否在编程复杂度和算法复杂度上找到⼀个平衡呢，答案是肯定的。

我们使⽤增⼴路的思想，⽽且必须进⾏优化。

因为原始的增⼴路算法（例如EK）是⾮常悲剧的。

基于网络流的路径规划算法研究一、引言路径规划是计算机科学领域中的一个重要研究方向，其目的是找到从一个起点到终点的最佳路径。

在现实生活中，路径规划在许多领域都有广泛应用，如交通导航、物流配送、机器人导航等。

网络流算法是一种常用于解决路径规划问题的方法，其基本思想是将路径规划问题转化为网络中最大流或最小割问题。

本文将从网络流算法的原理、应用和改进等方面进行深入研究。

二、网络流算法原理1.1 最大流问题最大流问题是一种经典的优化问题，在给定一个有向图和两个节点s和t时，其目标是找到从s到t的最大流量。

常用解决最大流问题的方法有Ford-Fulkerson算法和Edmonds-Karp算法。

Ford-Fulkerson算法通过不断寻找增广路径来增加当前流量，直到无法找到增广路径为止。

Edmonds-Karp算法在Ford-Fulkerson基础上进行了改进，使用BFS寻找增广路径，使得时间复杂度更低。

1.2 最小割问题最小割问题与最大流问题相对应，在给定一个有向图和两个节点s和t时，其目标是找到一个割集，使得割集中的节点可以通过流量的传递到达t，且割集的容量最小。

最小割问题可以通过最大流问题来解决，即找到最大流后，将图中所有边的容量减去其流量得到的边即为最小割。

三、网络流算法应用2.1 交通导航交通导航是路径规划应用中常见的场景之一。

通过将道路网络抽象为有向图，交通导航系统可以根据实时路况信息和用户目标位置，利用网络流算法求解出最短路径或者时间最短路径。

在实际应用中，还需要考虑一些约束条件如道路限速、拥堵情况等。

2.2 物流配送物流配送是另一个重要领域，在物资配送过程中需要考虑如何规划路径以减少时间和成本。

利用网络流算法可以将物资配送过程抽象为有向图，并根据货物数量、距离等因素求解出最优路径以实现高效配送。

2.3 机器人导航机器人导航是人工智能领域研究的热点之一，在机器人行走过程中需要规划路径以避开障碍物。

[学习笔记]⽹络最⼤流的HLPP算法#define u的伴点集合与u相隔⼀条边的且u能达到的点的集合0x00~ {}~PrefaceHLPP(Highest~Label~Preflow~Push)最⾼标签预流推进算法是处理⽹络最⼤流⾥两种常⽤⽅法——增⼴路&预流推进中，预流推进算法的⼀种。

据传由tarjan发明怎么⼜是他，并被其他科学家证明了其复杂度是紧却的O(n^2\sqrt m)。

在随机数据中不逊⾊于普通的增⼴路算法，⽽在精⼼构造的数据中⽆法被卡，所以是⼀种可以替代Dinic的⽅法（随我怎么说，代码⼜长⼜难调，所以还是Dinic好啊\rm{TAT}）但⽆论怎样，wiki⾥⾯已经承认HLPP是现在最优秀的⽹络流算法了。

那么预流推进这个⼤门类⾥⾯，思想都差不多。

⼤抵上就是我们对每个点记录超额流(Extra~Flow) ，即允许流在⾮源点暂时存储，并伺机将超额流推送出去。

不可推送的，就会流回源点。

那么最终答案显然存储在Extra[T]⾥⾯。

但同时这也有⼀个问题，就是会出现两个点相互推送不停的情况。

为了防⽌这样，我们采⽤最⾼标号的策略，给每个点⼀个⾼度，对于⼀个点u以及它的伴点集合\{v\}，当且仅当h_u = h_v + 1时才可以推送流。

并且我们对于源点S，设置h_S = N，并对于S实⾏⽆限制推送。

那么最后的答案就保存在Extra[T]⾥⾯。

但有时，我们发现有个点是”⾕“，即周围点的⾼度都⽐它⾼，但是它有超额流。

那么我们此时考虑拔⾼它的⾼度，即重贴标签(relabel)操作。

0x01\quad初步的算法流程以下我们⽤Extra_u表⽰u的超额流，h_u表⽰u的⾼度，⽤f_k表⽰边k的容量。

⾸先把所有的h_i都置为零，并把h_s置为N（点数）。

将S的流推送到每个与S相邻的点，同时把他们加⼊⼀个以⾼度为键值得⼤根堆，所以每次取出的应该是⾼度最⾼的、且超额流不为零的点，并执⾏推送操作。

对于点u推送过程中，如果Extra_u减到了0，就⽴即退出（优化⼀）对于每条出边k，推送的流量F = min(f_k,Extra_u)并执⾏两个点（u,v）的超额流增减。

网络流基本概念在实际生活中有许多流量问题，例如在交通运输网络中的人流、车流、货物流，供水网络中的水流，金融系统中的现金流，通讯系统中的信息流，等等。

50年代以福特(Ford)、富克逊(Fulkerson)为代表建立的“网络流理论”，是网络应用的重要组成部分。

在最近的奥林匹克信息学竞赛中，利用网络流算法高效地解决问题已不是什么稀罕的事了。

本节着重介绍最大流(包括最小费用)算法，并通过实际例子，讨论如何在问题的原型上建立—个网络流模型，然后用最大流算法高效地解决问题。

1.问题描述如图5-1所示是联结某产品地v1和销售地v4的交通网，每一弧(vi,vj)代表从vi到vj的运输线，产品经这条弧由vi输送到vj，弧旁的数表示这条运输线的最大通过能力。

产品经过交通网从v1到v4。

现在要求制定一个运输方案使从v1到v4的产品数量最多。

图5-1 图5-2 2.网络与网络流给一个有向图N=(V，E)，在V中指定一点，称为源点(记为vs，和另一点，称为汇点(记为vt)，其余的点叫中间点，对于E中每条弧(vi，vj)都对应一个正整数c(vi，vj)≥O(或简写成cij)，称为f的容量，则赋权有向图N=(V，E，c，vs，vt)称为一个网络。

如图5-1所给出的一个赋权有向图N就是一个网络，指定v1是源点，v4为汇点，弧旁的数字为cij。

所谓网络上的流，是指定义在弧集合E上一个函数f={f(vi，vj)}，并称f(vi，vj)为弧(vi，vj)上的流量(下面简记为fij)。

如图5-2所示的网络N，弧上两个数，第一个数表示容量cij，第二个数表示流量fij。

3.可行流与最大流在运输网络的实际问题中，我们可以看出，对于流有两个显然的要求：一是每个弧上的流量不能超过该弧的最大通过能力(即弧的容量)；二是中间点的流量为0，源点的净流出量和汇点的净流入量必相等且为这个方案的总输送量。

因此有：(1)容量约束：0≤f ij≤c ij，(v i,v j)∈E，(2)守恒条件对于中间点：流入量=流出量；对于源点与汇点：源点的净流出量v s(f)=汇点的净流入量（-v t(f)）的流f，称为网络N上的可行流，并将源点s的净流量称为流f的流值v(f)。