文档介绍：。可惜它给的测试数据几乎没有任何杀伤力,后面测试时我们采用DD_engi写的程序生成的加强版数据。总体上来说,最大流算法分为两大类:增广路(AugmentingPath)和预流推进重标号(PushRelabel)。也有算法同时借鉴了两者的长处,如ImprovedSAP。本篇主要介绍增广路类算法,思想、复杂度及实际运行效率比较,并试图从中选择一种兼顾代码复杂度和运行效率的较好方案。以下我们将会看到,有时理论分析的时间复杂度并不能很好的反映一种算法的实际效率。-Fulkerson方法所有增广路算法的基础都是Ford-Fulkerson方法。称之为方法而不是算法是因为Ford-Fulkerson只提供了一类思想,在此之上的具体操作可有不同的实现方案。给定一个有向网络G(V,E)以及源点s终点t,FF方法描述如下:Ford-Fulkerson方法(G,s,t)1将各边上流量f初始化为02while存在一条增广路径p3do沿路径p增广流量f4returnf假设有向网络G中边(i,j)的容量为c(i,j),当前流量为f(i,j),则此边的剩余流量即为r(i,j)=c(i,j)-f(i,j),其反向边的剩余流量为r(j,i)=f(i,j)。有向网中所有剩余流量r(i,j)0的边构成残量网络Gf,增广路径p即是残量网络中从源点s到终点t的路径。沿路径p增广流量f的操作基本都是相同的,各算法的区别就在于寻找增广路径p的方法不同。例如可以寻找从s到t的最短路径,或者流量最大的路径。-Karp算法ShortestAugmentingPath(SAP)是每次寻找最短增广路的一类算法,Edmonds-Karp算法以及后来著名的Dinic算法都属于此。SAP类算法可统一描述如下:ShortestAugmentingPath1x2while在残量网络Gx中存在增广路s~t3do找一条最短的增广路径P4delta5沿P增广delta大小的流量6更新残量网络Gx7returnx在无权边的有向图中寻找最短路,最简单的方法就是广度优先搜索(BFS),E-K算法就直接来源于此。每次用一遍BFS寻找从源点s到终点t的最短路作为增广路径,然后增广流量f并修改残量网络,直到不存在新的增广路径。E-K算法的时间复杂度为O(VE2),由于BFS要搜索全部小于最短距离的分支路径之后才能找到终点,因此可以想象频繁的BFS效率是比较低的。实践中此算法使用的机会较少。,而DFS又不能保证找到最短路径。1970年Dinic提出一种思想,结合了BFS与DFS的优势,采用构造分层网络的方法可以较快找到最短增广路,此算法又称为阻塞流算法(BlockingFlowAlgorithm)。首先定义分层网络AN(f)。在残量网络中从源点s起始进行BFS,这样每个顶点在BFS树中会得到一个距源点s的距离d,如d(s)=0,直接从s出发可到达的点距离为1,下一层距离为2...。称所有具有相同距离的顶点位于同一层,在分层网络中,只保留满足条件d(i)+1=d(j)的边,这样在分层网络中的任意路径就成为到达此顶点的最短路径。Dinic算法每次用一遍BFS构建分层网络AN(f),然后在AN(f)中一遍DFS找到所有到终点t的路径增广;之后重新构造AN(f),若终点t不在AN(f)中则算法结束。DFS部分算法可描述如下:1p2whiles的出度0do3u4ifu!=tthen5ifu的出度0then6设(u,v)为AN(f)中一条边7p8else9从p和AN(f),只需保存每个顶点的距离标号并在DFS时判断dist[i]+1=dist[j]即可。Dinic的时间复杂度为O(V2E)。由于较少的代码量和不错的运行效率,Dinic在实践中比较常用。具体代码可参考DD_engi网络流算法评测包中的标程,这几天dinic算法的实现一共看过和比较过将近10个版本了,DD写的那个在效率上是数一数二的,逻辑上也比较清晰。。通常的SAP类算法在寻找增广路时总要先进行BFS,BFS的最坏情况下复杂度为O(E),这样使得普通SAP类算法最坏情况下时间复杂度达到了O(VE2)。为了避免这种情况,Ahuja和Orlin在1987年提出了ImprovedSAP算法,它充分利用了距离标号的作用,每次发现顶点无出弧时不是像Dinic算法那样到最后进行BFS,而是就地对顶点距离