dinic的复杂度为O(n2m)O(n^2m)O(n2m)为啥那么多题都能解决啊,比如P1646点数为n2n^2n2,边数也为n2n^2n2,复杂度应为O((n2)2∗n2)O((n^2)^2*n^2)O((n2)2∗n2),应为O(n6)O(n^6)O(n6)可是这肯定不能过把。还有这题P1361也是一样的。
另外费用流复杂度oiwiki上写着是O(nmf)O(nmf)O(nmf),可是费用流板子的 f 很大啊,另外那个SSP算法用EK和dinic实现是一样复杂度的吗?