考虑，在具有整数圆弧容量的有向网络中存在一个非整数最大流量。
是否有一种算法可以将此流量转换为整数最大流量?
它的运行时间是多少?
这不是家庭作业
如果您正在寻找具有积分弧容量的最大s-t流量(整数)，则它不是np完全的。也许有这样的算法。你要做的就是找到一些没有饱和的电弧。在所有经过这条边的路径上，这条边必须是饱和的。这里有多条s-t路径它们的容量都是非积分的。试着通过增加一个，减少另一个来求积分违反容量。
另外，看看这个页面的算法:http://en.wikipedia.org/wiki/Maximum_flow_problem所有提到的算法都应该产生积分流。
还陈述了积分流定理:如果流网络中的每条边都有积分容量，则存在一个积分最大流量。
我不知道你说的convert this flow into an integer maximum flow是什么意思。如果你有一个非积分的最大流量，那么当然不可能从一个积分问题中得到相同的流量，因为整数图的解也是积分的。
(如。如果你的最大流量是3.5，没有办法从积分图中得到这个最大流量)。
如果你想要的只是整数图形的解决方案。再解一次，就得到相应的整数解。
PS:无论是整数还是非整数的最大流量都不是np完全的。
这类似于AMO书中的9.42练习。我认为最好看看"整数等流问题"