带顶点容量的最大流实现：非归约路径增广方法是否可行？

首先纠正一个关键逻辑错误：你这里搞反了——路径能承载的最大流量，应该是路径中所有边的最小容量与路径中所有中间顶点的最小容量的较小值，而非较大者。不管是边的容量限制，还是顶点的容量限制，都是流量的瓶颈：只要其中一个瓶颈存在，整个路径的流量就不能超过这个瓶颈值。

你的思路是否可行？ #

这个思路本身可以实现带顶点容量的最大流计算，但需要注意两个细节：

• 顶点容量的适用范围：通常源点和汇点不需要考虑顶点容量（流量从源点流出、汇入汇点，顶点容量一般限制流经中间顶点的流量）；如果你的场景中源汇也有容量限制，也要将它们纳入计算。
• 流量更新的同步：在增加路径流量后，除了像普通Ford-Fulkerson算法那样更新边的剩余容量，还要同步更新顶点的剩余容量——因为流经顶点的流量会占用它的容量配额。

不过这个思路相比维基百科的拆点归约方案，并没有本质优势，反而需要额外维护顶点容量的状态，代码复杂度更高。拆点方案的好处是可以直接复用现有不带顶点容量的最大流实现，无需修改核心算法逻辑。

算法复杂度是否保持不变？ #

如果你的实现是在原有Ford-Fulkerson的基础上，每次找增广路时多遍历一遍路径上的顶点来计算最小顶点容量，那么时间复杂度的阶数不会改变：

• 对于用DFS找增广路的普通Ford-Fulkerson，复杂度为$O(F \cdot E)$（F是最大流值，E是边数）。你的思路只是在每次找增广路后多了$O(P)$的计算（P为路径长度，最多为$O(V)$，V是顶点数），整体复杂度仍为$O(F \cdot (E+V))$，与原算法同阶。
• 如果用Dinic这类更高效的实现，只需在分层或找阻塞流时额外处理顶点容量，复杂度阶数也不会变化。

不过实际运行效率可能会因额外的顶点容量计算略有下降，但理论复杂度一致。

内容的提问来源于stack exchange，提问作者tonythestark