我写的消圈算法好像和通常意义上的还不太一样,据我了解,最原始的消圈算法是每次求最大流再在残量网络上消负环,然而我是先通过加一条 t 到 s 容量足够大费用足够小的边把问题转化成无源汇最小费用流(或者叫最小费用循环流),然后直接消负环。消的顺序是依次消掉包含每个点的所有负环。
这样应该是伪多项式且可以在当前数据范围内叉掉的吧(
提交:http://uoj.ac/submission/371127
加了点随机的提交:http://uoj.ac/submission/371132
求 hack /kel (或者指出在数据范围内叉不掉)