考虑一下，我们在具有整数弧容量的有向网络中有一个非整数最大流。
是否有算法可以将这个流量转化为整数最大流量？
它的运行时间是多少？
这不是作业问题。
最佳答案
如果您正在寻找具有积分弧容量的最大 s-t 流量(整数)，则它不是 NP 完全的。 也许有一个算法可以达到这个目的。你会尝试的是找到一些 容量未饱和的电弧。 在采用此边缘的所有路径上必须是饱和的边缘。 在这里，您将拥有多个具有非整数容量的 s-t 路径。 尝试通过增加一个并减少另一个而不 违反能力。
此外，请查看此页面上的算法: http://en.wikipedia.org/wiki/Maximum_flow_problem 所有提到的算法都应该产生积分流。
它还陈述了积分流定理: 如果流网络中的每条边都具有积分容量，则存在积分最大流。
关于算法题: Converting non-integer maximum flow to integer maximum flow，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5699360/