一、网络最大流

一般的做法是 $O(n^2m)$ 的 Dinic/ISAP 和 $O(n^2\sqrt m)$ 的 HLPP。

但是在所有边的流量上限都是 $1$ 的时候，存在 $O(n^{\frac{8}{3}}),O(m^{\frac{3}{2}})$ 的做法。

详见这里。

二、最小费用最大流

一般的做法是 $O(fmn)$ 的 SSP 和 $O(mn+fm\log m)$ 的 Primal Dual。

但是在所有正向边的单位费用都是非负数的情况下，存在 $O(f(m+n)\log(m+n))$ 的做法。

详见这里。

我觉得这一点很让人费解：如果所有正向边的单位费用都是非负数，并且不可能全图的所有边的单位费用都是 $0$，一定会存在一些正向边的单位费用是正数。那么如果要连反向边的话，反向边的单位费用一定是负数，那么这个 $O(f(m+n)\log(m+n))$ 是如何实现的？

我想知道上述 $3$ 种时间复杂度更优的算法具体是如何实现的（因为 CCF 的考试肯定不给用这个库），尤其是那个最小费用最大流。