algorithm - 最小成本流到最大流

Question

从最小成本流问题到最大流问题是否有减少？或相反亦然？我想使用最小成本流算法来解决最大流问题。

Answer 1

对不起，我想我第一次误解了这个问题。是的，最小成本是最大流量的一个特例。最小成本不是最大流量，而是假设在通过每条边之后，流量是有成本的。因此，如果您将每条边的成本设置为零，则最小成本会降低到最大流量。

编辑：

由于最低成本问题需要一个预定义的所需流程才能开始发送。c(u, v) = 0您将需要多次运行上述算法（成本为 edge ）以搜索最大值。对于给定的值范围，可以使用二分查找更有效地定位最大值

你是说Min Cut Max Flow吗？（编辑：我不认为你的意思是这个，但这是证明最大流量的基础，如果你没有的话值得一看）如果你放下一个图表并自己做一个最小切割，我会更容易理解。

Answer 2

为每条边添加 -1 的成本（每单位流量），然后使用最小成本算法。这将使流量最大化。

Answer 3

接受的答案可能是实用的。证明 Max-Flow 是 Min-Cost-Flow 的一个特例，还有另一种可能性。我的解决方案采用最小平均周期取消算法的一次迭代O(m^3 n^2 log n)（因为 c 不是保守的）：

1. set c(e) = 0 for all edges in G
2. add edge (t,s) with inf capacity and c((t,s)) = -1
3. start MIN-MEAN-CYCLE-CANCELLING on modified graph G'

正确性：算法正在搜索具有负权重的残差圆。只要存在从 s 到 t 的增广路径，就有负加权残差圆。