分配问题与成本

Question

我有一个问题，我是坚持了，并不能找到任何地方下手，所以我无可救药地转向计算器。

这个问题要我们看看它是NP难或多项式，如果NP难证明NP完全性，否则给出的算法。

问题如下：

的产物中存在的n个模块。有两家公司可以建立各个模块，具有一定的成本（c_ij，我：模块号，J：公司号码）。如果模块A和B是由不同的公司建造，他们也有一个额外的费用，（p_ab）。模块A和B不必是连续的，同样的额外费用适用于A和C太。正如所料，这个问题希望我们找到模块公司的分配，使总成本最小。

任何想法？

Answer 1

它可以降低到最小切割问题，其可以通过任何最大流算法找到。 那么什么是网络？ 模块将是我们图形的vertecies，也是我们添加2个新的顶点源和宿。 从源我们添加边缘与容量α1各模块我。同样从每一个模块我我们添加边容量C 12至下沉。同样对于任何模块i和j我们有能力圣战添加边缘 （面向图的因而将有两个边缘（I J）和（j i））的。这是很容易看到min切削该值是这个问题的解决方案（在与源分配给第二公司切口的部分的模块和模块休息到第一公司）