代码1:SAP单路增广(非递归);

代码2:SAP多路增广(递归);

代码3:Dinic单路增广(非递归);

代码4:Dinic多路增广(递归);

结果:

代码1:

代码2:

代码3:

 代码4:

结果:
SAP加了多路增广后,直接秒掉后2个点;
Dinic加了多路增广后效率差不多,还更低了一点……

(另外发现,SAP的多路增广不支持当前弧优化……这点和zkw费用流有点像囧……不过效率影响不大……)

Feedback

# re: profit是怎样被SAP的多路增广虐爆的……  回复  更多评论   

2011-07-13 10:31 by SHUXK
请问神牛的SAP算法有没有加当前弧优化??

# re: profit是怎样被SAP的多路增广虐爆的……  回复  更多评论   

2011-07-13 10:37 by Mato_No1
@SHUXK
单路增广加了,多路增广不能加。
另外本沙茶后来发现SAP其实是有缺陷的,在原图是一条链的情况下会退化到O(N^2),因此比赛时为了保险还是写Dinic吧囧……

# re: profit是怎样被SAP的多路增广虐爆的……[未登录]  回复  更多评论   

2011-09-25 17:23 by rtmiracle
那个啥,能否看一下你这四个程序?你用QQ传给我吧,谢谢

P.S. 你多少年没上QQ了,见不到你了,我是那个rtmiracleRP++

# re: profit是怎样被SAP的多路增广虐爆的……  回复  更多评论   

2012-02-20 16:27 by roosephu
似乎我写sap单路增广没事呀……0.30+s最大点

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理