Posted on 2011-03-19 17:55
Mato_No1 阅读(1190)
评论(4) 编辑 收藏 引用 所属分类:
算法效率实验 、
网络流
代码1：SAP单路增广（非递归）；
代码2：SAP多路增广（递归）；
代码3：Dinic单路增广（非递归）；
代码4：Dinic多路增广（递归）；
结果：
代码1：
代码2：
代码3：
代码4：
结果：
SAP加了多路增广后，直接秒掉后2个点；
Dinic加了多路增广后效率差不多，还更低了一点……
（另外发现，SAP的多路增广不支持当前弧优化……这点和zkw费用流有点像囧……不过效率影响不大……）