算法问题：将非整数最大流量转换为整数最大流量
考虑一下，我们在具有整数弧容量的有向网络中具有非整数最大流量。
有没有一种算法可以将这个流量转化为整数最大流量？
它的运行时间是多少？
这不是家庭作业的问题。
Consider, we have a non-integer maximum flow in a directed network with integer arc capacity.
Is there an algorithm that can convert this flow into an integer maximum flow?
And what is its running time?
It is not a homework problem.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这与 AMO 书中的练习 9.42 类似。我认为最好看看“整数等流问题”。
This is similar to the exercise 9.42 from AMO's book. I think it is better to look at "integer equal flow problem".
如果您正在寻找具有积分弧容量的最大 st 流量（整数），那么它不是 NP 完全的。
也许有一种用于此目的的算法。你会尝试的是找到一些
容量未饱和的电弧。
在采用该边缘的所有路径上，该边缘必须是饱和的边缘。
在这里，您将拥有多个具有非完整容量的 st 路径。
尝试通过增加一个并减少另一个来进行积分，而不需要
违反能力。
此外，请查看此页面上的算法：
http://en.wikipedia.org/wiki/Maximum_flow_problem
所有提到的算法都应该产生积分流。
它还陈述了积分流定理：
如果流网络中的每条边都有积分容量，则存在积分最大流。
If you are looking for a max s-t flow(integer) with integral arc capacities it is not NP-complete.
And maybe there is an algorithms for that purpose. What you would try is to find some
arcs that are not saturated with there capacity.
On all path that takes this edge has to be an edge that is saturated.
Here you will have multiple s-t paths with non-integral capacity.
Try to make the integral by increasing one and decrease the other without
violating the capacities.
Additionally, take a look at the algorithms at this page:
http://en.wikipedia.org/wiki/Maximum_flow_problem
All mentioned algorithms should produce integral flows.
It also states the Integral Flow Theorem:
If each edge in a flow network has integral capacity, then there exists an integral maximal flow.
我不确定
将此流量转换为整数最大流量是什么意思。如果您有一个非积分最大流，那么当然不可能从积分问题中获得相同的流，因为整数图的解也是积分的。
（例如，如果您的最大流量为 3.5，则无法从积分图中获得该最大流量）。
如果您只想要舍入整数图的解决方案。只要再解一次，就得到了对应的整数解。
PS：整数和非整数最大流都不是NP完全的。他们俩都在P。
Im not sure what you mean by
convert this flow into an integer maximum flow.If you have a non integral max flow then of course its not possible to get the same flow from an integral problem, as the solution of an integer graph is also integral.
(E.g. if you max flow is 3.5, there is no way to get this max flow from an integral graph).
If you want just the solution the rounded integer graph. Just solve it again, and then you got the corrosponding integer solution.
PS: Neither integer nor non-integer max flow is NP-complete. They are both in P.