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