怀疑有负权环……
by panda_2134 @ 2018-04-02 16:39:00
@[panda_2134](/space/show?uid=23865) emmm不能用原始对偶吗?
by Captain_Paul @ 2018-04-02 16:43:04
楼上神仙对话听不懂qwq
by Refun @ 2018-04-02 17:24:09
Orz
by Dispwnl @ 2018-04-02 17:40:06
@[Captain_Paul](/space/show?uid=43471) 如果有负权环的话，$s-t$最短路都不存在，任何增广路费用流算法都不能用……原始对偶证明里面就假定了不存在负环的……
by panda_2134 @ 2018-04-02 17:51:55
@[panda_2134](/space/show?uid=23865) 哦这样啊谢了
by Captain_Paul @ 2018-04-02 18:54:09
@[panda_2134](/space/show?uid=23865) 不过可以通过建图技巧来避开负权环，预先流满。《训练指南》讲了的
by panda_2134 @ 2018-04-02 19:32:11