Dinic算法

‘壹’ 网络流的最大流算法

1、augment path，直译为“增广路径”，其思想大致如下：
原有网络为G，设有一辅助图G'，其定义为V(G') = V(G)，E(G')初始值（也就是容量）与E(G)相同。每次操作时从Source点搜索出一条到Sink点的路径，然后将该路径上所有的容量减去该路径上容量的最小值，然后对路径上每一条边<u,v>添加或扩大反方向的容量，大小就是刚才减去的容量。一直到没有路为止。此时辅助图上的正向流就是最大流。
我们很容易觉得这个算法会陷入死循环，但事实上不是这样的。我们只需要注意到每次网络中由Source到Sink的流都增加了，若容量都是整数，则这个算法必然会结束。
寻找通路的时候可以用DFS，BFS最短路等算法。就这两者来说,BFS要比DFS快得多，但是编码量也会相应上一个数量级。
增广路方法可以解决最大流问题，然而它有一个不可避免的缺陷，就是在极端情况下每次只能将流扩大1（假设容量、流为整数），这样会造成性能上的很大问题，解决这个问题有一个复杂得多的算法，就是预推进算法。
2、push label，直译为“预推进”算法。
3、压入与重标记(Push-Relabel)算法
除了用各种方法在剩余网络中不断找增广路(augmenting)的Ford-Fulkerson系的算法外，还有一种求最大流的算法被称为压入与重标记(Push-Relabel)算法。它的基本操作有：压入，作用于一条边，将边的始点的预流尽可能多的压向终点；重标记，作用于一个点，将它的高度（也就是label）设为所有邻接点的高度的最小值加一。Push-Relabel系的算法普遍要比Ford-Fulkerson系的算法快，但是缺点是相对难以理解。
Relabel-to-Front使用一个链表保存溢出顶点，用Discharge操作不断使溢出顶点不再溢出。Discharge的操作过程是：若找不到可被压入的临边，则重标记，否则对临边压入，直至点不再溢出。算法的主过程是：首先将源点出发的所有边充满，然后将除源和汇外的所有顶点保存在一个链表里，从链表头开始进行Discharge，如果完成后顶点的高度有所增加，则将这个顶点置于链表的头部，对下一个顶点开始Discharge。
Relabel-to-Front算法的时间复杂度是O(V^3)，还有一个叫Highest Label Preflow Push的算法复杂度据说是O(V^2*E^0.5)。我研究了一下HLPP，感觉它和Relabel-to-Front本质上没有区别，因为Relabel-to-Front每次前移的都是高度最高的顶点，所以也相当于每次选择最高的标号进行更新。还有一个感觉也会很好实现的算法是使用队列维护溢出顶点，每次对pop出来的顶点discharge，出现了新的溢出顶点时入队。
Push-Relabel类的算法有一个名为gap heuristic的优化，就是当存在一个整数0<k<V，没有任何顶点满足h[v]=k时，对所有h[v]>k的顶点v做更新，若它小于V+1就置为V+1。
cpp程序: #include<cstdio>#include<cstring>#include<algorithm>#include<queue>#;inttt,kase;intnn,m;intH[45],X[1004],P[1004],flow[1004],tot,cap[1005];intd[45];intS,T;voidadd(intx,inty,intz){P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;cap[tot]=flow[tot];}queue<int>q;boolbfs(){memset(d,0,sizeof(d));d[S]=1;intx;q.push(S);while(!q.empty()){x=q.front();q.pop();for(inti=H[x];i;i=X[i]){if(flow[i]>0&&!d[P[i]]){d[P[i]]=d[x]+1;q.push(P[i]);}}}returnd[T];}intdfs(intx,inta){if(x==T||a==0)returna;intf=a,tmp;for(inti=H[x];i;i=X[i]){if(flow[i]>0&&d[P[i]]==d[x]+1){tmp=dfs(P[i],min(flow[i],a));flow[i]-=tmp;a-=tmp;flow[i^1]+=tmp;if(!a)break;}}if(f==a)d[x]=-1;returnf-a;}intDinic(){intf=0;while(bfs())f+=dfs(S,inf);returnf;}intmain(){/**输入过程省略**/intmaxflow=Dinic();printf(%d ,maxflow);return0;}

‘贰’ sap算法的算法介绍

如果能让每次寻找增广路时的时间复杂度降下来，那么就能C了，使用距离标号的最短增广路算法就是这样的。所谓距离标号，就是某个点到汇点的最少的弧的数量（另外一种距离标号是从源点到该点的最少的弧的数量，本质上没什么区别）。设点i的标号为D[i]，那么如果将满足D[i]=D[j]+1的弧(i,j)叫做允许弧，且增广时只走允许弧，那么就可以达到“怎么走都是最短路”的效果。每个点的初始标号可以在一开始用一次从汇点沿所有反向边的BFS求出，实践中可以初始设全部点的距离标号为0，问题就是如何在增广过程中维护这个距离标号。
维护距离标号的方法是这样的：当找增广路过程中发现某点出发没有允许弧时，将这个点的距离标号设为由它出发的所有弧的终点的距离标号的最小值加一。这种维护距离标号的方法的正确性我就不证了。由于距离标号的存在，由于“怎么走都是最短路”，所以就可以采用DFS找增广路，用一个栈保存当前路径的弧即可。当某个点的距离标号被改变时，栈中指向它的那条弧肯定已经不是允许弧了，所以就让它出栈，并继续用栈顶的弧的端点增广。还有一种在常数上有所优化的写法是改变距离标号时把当前弧设为那条提供了最小标号的弧。当前弧的写法之所以正确就在于任何时候我们都能保证在邻接表中当前弧的前面肯定不存在允许弧。
还有一个常数优化是在每次找到路径并增广完毕之后不要将路径中所有的顶点退栈，而是只将瓶颈边以及之后的边退栈，这是借鉴了Dinic算法的思想。注意任何时候待增广的“当前点”都应该是栈顶的点的终点。这的确只是一个常数优化，由于当前边结构的存在，我们肯定可以在O(n)的时间内复原路径中瓶颈边之前的所有边。

‘叁’ 请问求最大流的时间复杂度最小的算法是哪一种

理论上是最高标号预流推进,英语缩写HLPP
但是实现较复杂
实践发现你把dinic和sap学了应该不会出先这两种都过不去的程序设计题目,要注意sap的优化

‘肆’ 网络流之最大流，您只需判断这个代码是属于哪一种最大流算法即可。

Edmonds - Karp 算法
最简单的增广路类算法，每次用一个 BFS 寻找最短增广路
while(1) 里前半部分的 for 循环就是 BFS 部分，队列 que[] 辅助进行 BFS，找到的增广路存在 pre[i] 中
if(!pre[sink])判断是否存在可到达汇点的增广路，不存在就跳出循环
后半部分 for 循环对找到的路径进行增广操作。

时间复杂度 O(VE^2)，行数虽少，但效率不是很高的算法

最后说一句，这代码风格太差了 = =，只考虑代码长度完全不顾可读性

参考资料是自己的 blog 呵呵

‘伍’ 数学建模网络流算法重要吗你们都用什么算法呢

1、蒙特卡罗算法（该算法又称随机性模拟算法，是通过计算机仿真来解决问题的算法，
同时可以通过模拟可以来检验自己模型的正确性，是比赛时必用的方法）
2、数据拟合、参数估计、插值等数据处理算法（比赛中通常会遇到大量的数据需要处理，
而处理数据的关键就在于这些算法，通常使用matlab作为工具）
3、线性规划、整数规划、多元规划、二次规划等规划类问题（建模竞赛大多数问题属于最优化问题，
很多时候这些问题可以用数学规划算法来描述，通常使用lindo、lingo软件实现）
4、图论算法（这类算法可以分为很多种，包括最短路、网络流、二分图等算法，
涉及到图论的问题可以用这些方法解决，需要认真准备）
5、动态规划、回溯搜索、分治算法、分支定界等计算机算法（这些算法是算法设计中比较常用的方法，很多场合可以用到竞赛中）
6、最优化理论的三大非经典算法：模拟退火法、神经网络、遗传算法
（这些问题是用来解决一些较困难的最优化问题的算法，对于有些问题非常有帮助，
但是算法的实现比较困难，需慎重使用）
7、网格算法和穷举法（网格算法和穷举法都是暴力搜索最优点的算法，在很多竞赛题中有应用，
当重点讨论模型本身而轻视算法的时候，可以使用这种暴力方案，最好使用一些高级语言作为编程工具）
8、一些连续离散化方法（很多问题都是实际来的，数据可以是连续的，而计算机只认的是离散的数据，因此将其离散化后进行差分代替微分、求和代替积分等思想是非常重要的）
9、数值分析算法（如果在比赛中采用高级语言进行编程的话，那一些数值分析中常用的算法比
如方程组求解、矩阵运算、函数积分等算法就需要额外编写库函数进行调用）
10、图象处理算法（赛题中有一类问题与图形有关，即使与图形无关，论文中也应该要不乏图片的，
这些图形如何展示以及如何处理就是需要解决的问题，通常使用matlab进行处理）

‘陆’ Dinic算法的算法介绍

1、根据残量网络计算层次图。
2、在层次图中使用DFS进行增广直到不存在增广路。
3、重复以上步骤直到无法增广。 ProgramDinic;TypeLx=Array[0..50]OfLongint;VarLu:Lx;A,B:Array[0..50]OfLx;D,Dist:LX;V,T:Array[0..50]OfBoolean;Head,Tail,Sum,Ans,X,Y,S,I,P,J,K,M,N:Longint;Q,C:Boolean;ProcereSpfa(S:Longint);VarI,J,Now,Sum:Longint;BeginFillchar(D,Sizeof(D),0);Fillchar(V,Sizeof(V),False);ForJ:=1ToNDoDist[J]:=MaxLongint;Dist[S]:=0;V[S]:=True;D[1]:=S;Head:=1;Tail:=1;WhileHead<=TailDoBeginNow:=D[Head];ForI:=1ToB[Now,0]DoifA[Now,B[Now,I]]>0thenIf(Dist[B[Now,I]]>Dist[Now]+1)ThenBeginDist[B[Now,I]]:=Dist[Now]+1;IfNotV[B[Now,I]]ThenBeginInc(Tail);D[Tail]:=B[Now,I];V[B[Now,I]]:=True;End;End;Inc(Head);End;End;ProcereDfs(X,D:Longint);VarI:Longint;BeginLu[D]:=X;T[X]:=True;IfX=NThenBeginC:=False;S:=D;End;ForI:=1ToNDoIf(A[X,I]>0)AndCAnd(NotT[I])And(Dist[X]+1=Dist[I])ThenDfs(I,D+1);End;ProcereExpand(L:Lx;Len:Longint);VarI,J,K:Longint;BeginK:=MaxLongint;ForI:=2ToLenDoIfK>A[L[I-1],L[I]]ThenK:=A[L[I-1],L[I]];Sum:=K;Writeln('K=',K);ForI:=2ToLenDoBeginDec(A[L[I-1],L[I]],K);Inc(A[L[I],L[I-1]],K);End;End;BeginRead(N,M);ForI:=1ToMDoBeginRead(X,Y,K);A[X,Y]:=K;Inc(B[X,0]);B[X,B[X,0]]:=Y;End;C:=False;WhileTrueDoBeginSpfa(1);ForI:=1ToNDoT[I]:=False;K:=MaxLongint;C:=True;Dfs(1,1);IfCThenBreak;Expand(Lu,S);Inc(Ans,Sum);End;Writeln(Ans);End.

‘柒’ 谁懂网络流算法

1.Fort_Fulkerson算法. 2.Edmonds_Karp算法. 3.Push_Relabel 算法 4.Relabel_to_Front算法.

<<算法艺术与信息学竞赛>>上介绍了五种算法.

1.Fort_Fulkerson算法. 2.最短增广路算法. 3.使用距离标号的最短增广路算法. 4.预流推进算法 5.最高标号的预流推进算法.

<<实用算法分析与程序设计>>上介绍了一种算法:

1.Dinic算法.

另外在网上又看见一些其它算法:

1.SAP算法. 2.pre_flow 算法 3.FIFO pre_flow算法 。。。 。。。

其实不少算法说的都是同一个东西，只是名称不一样，现在总结如下:

1.Fort_Fulkerson算法.

2.Edmonds_Karp算法(最短增广路算法).-------------------O( n*m^2 )

3.SAP算法(使用距离标号的最短增广路算法).--------------O( n^2*m )

4.Dinic算法.------------------------------------------------------O( n^2*m )

5.Push_Relabel算法(预流推进算法).------------------------O( n^2*m )

6.FIFO Preflow_Push算法.------------------------------------O( n^2*m)

7.Relabel_to_Front算法.---------------------------------------O( n^3 )

8.Highest Label Preflow_push算法.--------------------------O( n^2*m^1/2)

‘捌’ cmd5x算法是什么意思

Dinic算法（又称Dinitz算法）是一个在网络流中计算最大流的强多项式复杂度的算法，设想由以色列（前苏联）的计算机科学家Yefim (Chaim) A. Dinitz在1970年提出。 算法的时间复杂度类似于Edmonds–Karp算法，其时间复杂度为，Dinic算法与Edmonds–Karp算法的不同之处在于它每轮算法都选择最短的可行路径进行增广。Dinic算法中采用高度标号（level graph）以及阻塞流（blocking flow）实现其性能。