网站的整体结构,建设银行淮安招聘网站,wordpress用qq群发,湖南建筑信息网首页这段时间复习了下网络流模型#xff0c;感觉比以前的理解有了长足进展#xff0c;虽然我知道这东西难就难在建模上#xff0c;而它的算法本身其实难度不大#xff0c;但我还是决定说一些我的理解#xff0c;毕竟理解了本质的东西运用起来才会更灵活。最大流的求解一般有两…这段时间复习了下网络流模型感觉比以前的理解有了长足进展虽然我知道这东西难就难在建模上而它的算法本身其实难度不大但我还是决定说一些我的理解毕竟理解了本质的东西运用起来才会更灵活。 最大流的求解一般有两类算法用费用流附带求出的不列入考虑范围就是增广路FF系列和预流推进PF系列。在很多地方都看到推荐使用后者因为效率更高但其实不然今天我这篇文章就是要重点介绍前者相信大家看了过后也会喜欢它的。 首先那些一大堆的关于网络的定义我就不说了不明白的就先去看看书好了我们约定S是源T是汇G表示残余图。增广路算法其实相当好理解因为只要在G中存在一条从S到T的通路那沿这条路走流量一定还可以增加所以当求得最大流的时候一定不存在S-T通路。 那反过来成立么显然因为我们有最小割最大流定理所以由此就得到了FF算法的基本方法 不断的在G中找一条S-T通路然后沿其增广直到无法找到。 至于用什么方法去找一条路那就随便了BFSDFS甚至A*你可以把你能想到的方法试个遍看看哪个合胃口就用哪个吧。 注意那个用BFS的方法它的官方名字叫Edmonds-KarpEK它和我们后面要说的费用流有很大的关系这里先简单提示一下。 那这方法的复杂度呢如果是整数流事实上分数流的话可以构造数据让FF无法停止这时候必须用到PF的方法显然每次至少增广1的流量每次查找O(E)条边增广要O(V)的时间因此复杂度为O((mn)*U)U是最大流。 听上去很恐怖其实EK算法的一个稍微精确的上界是O(VE^2)还是很夸张。 那么怎样才能跑得更快呢想想每次用BFS求出的Shortest Path TreeSPT我们只关心了S-T最短路其实还有很多信息没有利用到那么如果求一次SPT我们可以增广多次的话是不是会好些 于是引入层次图的概念说通俗点就是求G的SPT把G中每个顶点的距离S的标号d给求出来保留所有的s-t中d[s]1d[t]的边注意可以不是SPT中的边最后再在层次图中用多次BFS把所有的增广路求出来增广。 这样看似更快了其实没有因为分析复杂度依然是O(VE^2)没有改进而且我们还要写更多的代码。那瓶颈在哪里呢对了就是那步在层次图中用BFS来找增广路。其实更好的方法是用DFS一次就可以把所有的增广路求出来具体做法如下 从S开始做DFS一旦发现一条增广路于是就沿其增广然后DFS回退到离S最近的一条满流的边的起点处并在图中删除该边的终点继续搜索。 上面的算法就是著名的Dinic算法它的复杂度为O(EV^2)注意看清楚2的位置对于密图有不小的改进。 事实上我非常推荐在各类比赛中用Dinic算法因为它实现简单而且实际运行速度快比起PF算法好写太多了 那单纯的说好还是不行要拿出依据来。关于PF算法的理论在本文中就不详细叙述了可能以后我会专门介绍它。一般的PF实现是O(V^4)的而Relable-To-Front是O(V^3)高标推进据称是O(V^2*sqrt(E))虽然它实际中确实比较快但是PF的算法都有一个缺点就是必须加启发优化至少是Gap优化否则实际中会比较慢。因此写一个PF的代码自然就比较多了。 上面基本上把最大流的算法盘点了一下下面还是说一下最小费用流问题。 如果一个网络的边不仅有容量还有单位流量费用的话那我们自然想在求得最大流的同时使总费用更低。因此最小费用流实际上是一个更通用的模型因而其应用也更广。 令 人惊奇的是解决该问题可以不需要先求出最大流来当然也有方法需要所以如果你不想记那么多算法的话只知道该算法也没问题。因为费用流的算法如果说复 杂的话可以把线性规划扯近来所以先罗列下几个基本方法然后介绍最简单的一种其它的如果你有兴趣可以自己找文章来看 1、 连续最短路算法Successive Shortest Path 2、 消圈算法Cycle Canceling 3、 原始对偶算法Primal Dual 4、 网络单纯形Network Simplex。 后面的两个分别是前面两个的高级优化版本其基本的优化思路就是和我们上面论述的优化增广类似就是希望每次都能做几次运算不要一次用了就丢弃了。最好用的就是第一个方法方法二在Algorithm in C图论部分有详细论述我就不说了。 还记得刚才我说的EK么其实如果我们用Dijkstra在G中找S-T最短路而不是BFS的话是不是就解决问题了呢是的完全正确我把证明留给大家想其实很简单。 但是有个问题在G中存在负权的边用Dijkstra是不是不行了呢非要用Bellman-Ford么其实不然只要原图中没有负环存在有的话不存在最小费用那么我们可以利用Johnson算法的重赋权技术把所有的边先变成正权然后以后每次增广后再维护一下不就可以用高效的Dijkstra了算法如下 用Bellman-Ford求各点到S的高度标号d[] 以后每求一次最短路设标号为pi[]那么执行 For i1 to v do d[v]pi[v] 这样一来标号就一直合法了具体证明还是留给大家吧。 好了说这么多理论下篇文章将会说几个具体的题目加深对算法的理解。 转载于:https://www.cnblogs.com/zen_chou/archive/2009/07/16/1525185.html
