Posted on 2011-03-19 17:55
Mato_No1 閱讀(1201)
評論(4) 編輯 收藏 引用 所屬分類:
算法效率實驗 、
網絡流
代碼1：SAP單路增廣（非遞歸）；
代碼2：SAP多路增廣（遞歸）；
代碼3：Dinic單路增廣（非遞歸）；
代碼4：Dinic多路增廣（遞歸）；
結果：
代碼1：
代碼2：
代碼3：
代碼4：
結果：
SAP加了多路增廣后，直接秒掉后2個點；
Dinic加了多路增廣后效率差不多，還更低了一點……
（另外發現，SAP的多路增廣不支持當前弧優化……這點和zkw費用流有點像囧……不過效率影響不大……）