algorithm - 图表中的最小破坏成本

Question

我们得到一个图 G(V,E)，有 N 个节点(从 0 到 N-1 编号)和恰好 (N-1) 个双向边.

图中的每条边都有一个正成本 C(u,v)(边权重)。

整个图任何一对节点之间都有唯一路径。

我们还得到了一个列表L，其中放置了炸弹。

我们的目标是从图中破坏/移除边，在破坏/移除图中的边之后，炸弹之间没有联系——

即破坏后，任意两颗炸弹之间没有路径。

损坏边缘的成本(u,v) = 边缘权重(u,v)。

因此，我们必须损坏这些边缘，以使总损坏成本最小。

例子:

Total Nodes=N=5 
Total Bomb=Size of List L=3

List L={2,4,0}//Thats is at node number 2,4 and 0 bomb is placed...

Total Edges =N-1=4 edges are::

u v Edge-Weight

2 1 8

1 0 5

2 4 5

1 3 4



In this case the answer is ::
Total Damaging cost =(Edge Weight (2,4) + Edge Weight(0,1))
           =5+5=10.

So when we remove the edge connecting node (2,4),
and the edge connecting node (0,1) ,there is no connection left 
between any pair of machines in List {2,4,0};

Note any other,combinations of edges(that  we damaged ) to achieve the
target goal ,needs more than 10 unit cost.  

Constraints::
N(ie. Number of Nodes) <= 100,000
ListSize |L|(ie. Number of Bombs) <= N
1 <=Edge cost(u,v) <= 1000,000

我做了什么？

直到现在，我还没有找到任何有效的方法:( .

此外，由于节点数为 N，因此边数恰好为 N-1 并且整个图在任何对之间存在唯一路径的节点，我得到的结论是图是一棵树。

我尝试修改 Kruskal 算法，但这对我也没有帮助。

谢谢!

Answer 1

我认为修改后的 Kruskal 是解决问题的方法。

取图 G'=(V', E'), V'=V, E'={}。 按成本的非递增顺序对 E 中的边进行排序。 现在，对于 E 中的每条边，将其添加到 E' 当且仅当它不连接两个都具有带有炸弹的顶点的组件。 结果为E-E'成本之和。

编辑:

在您的示例上运行它。

最初，我们的边集是空的{}，我们将边按非递增顺序排序[(1, 2), (0, 1), (2, 4), (1, 3)]

因此，一开始，我们的图表由 5 个不相连的部分组成。

(1, 2) 的成本为 8，它连接的组件中只有一个有炸弹。所以我们将它添加到 E'。 E'={(1, 2)} 并且我们有 4 个组件。

下一个成本最高的边是 (0, 1)，成本为 5。但是两个组件都有炸弹，所以不要添加这条边。

下一个是 (2, 4)。这也连接到带有炸弹的组件，所以我们也跳过它。

最后成本最低的边是 (1, 3)。由于其组件之一(仅包含节点 3)没有炸弹，我们将其添加到 E'。

这给了我们 E' = {(1,2), (1, 3)}。

我的理由是我们尝试在添加成本较低的边之前添加成本较高的边 - 这确保在原始节点中有炸弹的节点之间的任何路径中，除了最低成本之外的所有路径都将被添加。