重新建模最大流-损失负边权的最小代价

Question

假设我有一个问题简化如下：

“生产者Pi可以按每项成本ci生产一定数量的产品ai，而消费者Ck可以以每项pk的利润消费金额bk。

我们对最大增益/最小损耗的最大流感兴趣，我们打算使用BGL的权重或它的取消来获得它。

我们应该能够通过将源S连接到具有容量ai边缘和ci权重的每个Pi来对其进行建模。

然后，我们将每个Pi连接到具有容量bk和加权-pk边缘的每个Ck。

最后，我们将每个Ck连接到具有容量bk和代价0边缘的目标T。

在该图上运行cycle_canceling后，我们可以得到两个值：maxflow将产生最大销售量，-mincost将表示总收益/损失。

我们显然不能使用successive_shortest_path_nonnegative_weights，因为-嗯，名称已经声明了它。

但是，我注意到，cycle_canceling比successive_shortest_path方法慢得多，通过重新构造问题，我们可以消除负权重。

然而，我不知道如何重新设计这个。显然，我们不能简单地在所有的边权值中添加一个常数，因为这会改变最短路径，从而伪造结果。然而，我们必须以某种方式反映这样一个事实:取取某些边缘会增加总成本，而其他成本则会因此而减少。

有什么暗示吗？

Answer 1

这对于最小成本的最大流量来说是个奇怪的问题。最好是按成本增加对生产者进行排序，按利润下降对消费者进行排序，然后只要有收益，就反复让第一剩余生产者发送给第一剩余消费者。如果你想变得超级漂亮，有一个O(n)-time算法，类似于你最喜欢的中值查找算法。

编辑:因为使用最小成本最大流有隐藏的原因(请不要养成这种习惯；算法设计特别容易出现XY问题)，所以您可以做的是按如下方式调整弧的权重(这是一个标准技巧，例如Johnson的算法)。

使用一种可以处理负重的算法(例如Bellman--Ford)来计算从S到每个顶点v的距离d(v)，现在更新弧形u->v到d(u) + w(u->v) - d(v)的权重w(u->v)，这保证是非负的，而从S到T的每条路径的总相对重量保持不变，直到一个加性常数(d项望远镜)。