@[xiaoyaohanzi](/user/607785) 如果所有边容量都是 1，那么单次网络流的复杂度上界是 $O(m\times\min\{m^{\frac12},n^{\frac23}\})$；进一步，如果还满足对于每个源汇以外的点都满足入度与出度至少一个为 1，那么复杂度可以进一步分析到 $O(m\sqrt n)$，这个情况一般是出现在二分图匹配中。
by UnyieldingTrilobite @ 2023-07-27 23:21:26