UOJ Logo ouuan的博客

博客

求 hack 费用流消圈算法

2019-11-09 11:40:35 By ouuan

我写的消圈算法好像和通常意义上的还不太一样,据我了解,最原始的消圈算法是每次求最大流再在残量网络上消负环,然而我是先通过加一条 t 到 s 容量足够大费用足够小的边把问题转化成无源汇最小费用流(或者叫最小费用循环流),然后直接消负环。消的顺序是依次消掉包含每个点的所有负环。

这样应该是伪多项式且可以在当前数据范围内叉掉的吧(

提交:http://uoj.ac/submission/371127

加了点随机的提交:http://uoj.ac/submission/371132

求 hack /kel (或者指出在数据范围内叉不掉)

评论

142857cs
还有似乎cost-scaling的复杂度也是不对的,不过我不知道怎么卡。。。

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。