Posts tagged SAP

网络流的几个常见算法

31
884 天
by in Algorithm

最近研究了一下网络流.最常见的几个算法有下边几种
一:增广路算法
在残余网络中不断的找增广路

  1. Ford-Fulkerson

    2. 很不幸,这是一个用dfs找任意增广路的算法.时间复杂度无从估计

  2. Edmonds-Karp

    3. 用bfs代替了dfs寻找增广路,悲观的时间复杂度是O(VE2)

  3. Dinic

    4. 据说和SAP很像,还没研究,O(V2E)

  4. Shortest Augmenting Paths(也就是很流行的SAP算法)

    5. 故名思议,就是找最短的增广路,把EK算法的O(E)时间优化到了O(V),故复杂度为O(V2E)
    不过加了间隙优化后效率和Dinic不可同日而语

二:预留推进算法
非常形象的灌水机制,一开始源点在最高,向各个管道灌水,如果一个点有盈余,那么它必需往低处流(Push),不能留的话上升高度(Relabel)后再往低处流

  1. Push_Relabel

    2. 很朴实的预留推进算法,O(V4)

  2. Relabel_to_Front

    3. 用一个List维护各个点,当一个点被relabel后回到List首部(to front)再往后计算,O(V3)

  3. Highest_Relabel(不知道这是不是传说中的HLPP算法–Highest_Label_Preflow_PushO(V2E1/2))

    4. Relabel_to_Front的改进版,List分层从最高的点开始流,并且加上BFS预处理和间隙优化后效率会有不可思议的提高

据说还有一些复杂度非常奇怪的算法:VElogE/(V/logV)(V)、min(V2/3,E1/2)Elg(V2/E+2)lgC…..
(更多…)

Popularity: 22% [?]

网络流专辑

21
896 天
by in Special Topic

网络流是ACM里非常重要的一大块,变形非常灵活,这些天仅仅只是做了一点点题目,几个经典模型,冰山一角而已.
图论可不是练两天就能掌握的,所以也就放弃了一口吃成胖子的想法,打一场持久战,有空的时候更新几道并在下边写点解题报告,所以暂时不可能成为一篇非常完整的整理
所以我在下文加了几个相关链接,都是大牛们的整理,并且也有这对题目的相关分析…
(更多…)

Popularity: 25% [?]

Page 1 of 11
Go to Top