带权边的最大分布

Question

设想一个图，其中每个顶点都有一个值(例如，石头的数目)，并通过边连接起来，这表示在石头中遍历该边的成本。我想找出最大可能数量的石头，这样每个顶点Vn >=这个值。顶点可以将石头交换给其他人，但交换的值被连接它们的边的距离或重量减去。

我需要解决这个贪婪的算法和在O(n)复杂性，其中n是顶点的数量，但我有问题，识别子问题/贪婪的选择。我希望有人能提供一个垫脚石或一些如何完成这一点的提示，非常感谢。

Answer 1

问题摘要

我不确定我是否正确地理解了这个问题，所以首先我要总结一下我的理解。

1. 我们有一个具有顶点v1，v2，..，vn和加权边的图。设vi和vj之间的重量是Wi，j。
2. 每个顶点从若干个石头开始，让我们将顶点vi上的石头数称为Ai。
3. 您希望执行多个传输，以便最大化min的值(Ai表示i=1.n)
4. 如果x>Wi，j，此操作可以在vi和vj之间传输X石，此操作将值转换为：

Ai -= x Aj += x-Wi，j#注意到达的石头比离开的少

这是正确的吗？

响应

我认为这个问题是NP难的，因为它可以用来解决3-SAT，一个已知的NP-完全问题。

对于具有M子句的3-sat示例，如：

(A+B+!C).(B+C+D)

构造一个有向图，其中每个子句有一个节点(没有石头)，每个变量有3M+1石，每个变量有两个辅助节点，每个变量有一个1石(一个代表具有一个正值的变量，另一个代表具有负值的变量。

然后连接节点，如下所示：

​

​

这个图将有一个解，所有顶点都有值>= 1，当且仅当3-sat是可溶的。

关键是每个红色节点(例如变量A)只能向A=1或A=0发送石头，而不能同时发送两者。如果我们向绿色节点A=1提供石头，那么这个节点就可以为所有使用该变量的蓝色子句提供正向的支持。

(您最初的问题并不涉及有向图，但我怀疑这种额外的更改是否会对问题的复杂性产生重大影响。)

摘要

恐怕很难得到这个问题的O(n)解。