在图中的最小损害成本

本文介绍了在图中的最小损害成本的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我们都给出了图G（V，E）有N个节点（编号从0到N-1），准确（N-1）的的双向边的。

We are given a graph G(V,E) with N nodes (Numbered from 0 to N-1) and exactly (N-1) two-way Edges.

在图中的每个边缘有一个确定的成本C（U，V）（边的权重）。

Each edge in a graph has a positive cost C(u,v)(Edge weight).

整个图形是这样的：有任何对节点的

The entire graph is such that there is a unique path between any pair of Nodes.

我们也给出一个List →的节点号，在该炸弹被放置。

We are also given a List L of node number,at which bomb are placed.

我们的目标是为破坏/删除边缘从图中这样，那以后破坏性/从图中移除边，有炸弹之间没有连接 -

Our aim is to damage/remove the edge from the graph such ,that after damaging/removing the edges from the graph ,there is no connection among the Bombs --

这是破坏后，有任何两弹

损坏边缘的成本（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

我做了什么？

到现在为止，我还没有找到任何有效的方法:(。

Until now, I had not found any efficient way :( .

此外，由于节点数量为 N ，边数恰好是 N-1 和整个图形就是这样存在任何对节点之间的唯一路径，我得到一个结论，即的图是一个的乔木的

Further, as the number of nodes is N, the number of edges is exactly N-1 and the entire graph is such there is a Unique path between any pair of Nodes, I got a conclusion that the graph is a TREE.

我试图修改克鲁斯卡尔算法，但并没有帮助我满意。

I tried to modify the Kruskal algorithm but that didn't help me either.

谢谢！

Chopra

在图中的最小损害成本

问题描述

推荐答案