图表中的最小损坏成本

Question

我们给出了具有N个节点(从0到N-1编号)和精确(N-1)双向边缘的图G(V,E).

图中的每条边具有正成本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,并且整个图形是这样的,在任何节点对之间存在唯一路径,我得出结论图形是TREE.

我试图修改Kruskal算法,但这也没有帮助我.

谢谢!

Answer 1

这就是树木的多路切割问题。它可以通过简单的动态规划在多项式时间内求解。参见 Chopra 和 Rao：“论多路切割多面体”，Networks 21(1):51\xe2\x80\x9389，1991。

\n