Минимальные разрушающие затраты на графике
Нам дан граф G (V, E) с N узлами (пронумерованными от 0 до N-1) и точно (N-1)two-way Edges.
Каждое ребро в графе имеетpositive cost C(u,v)(Крайний вес).
The entire graph is such that there is a unique path between any pair of Nodes.
Нам также дают списокL номера узла, на котором размещена бомба.
Нашей целью являетсяdamage/remove the edge из графика так, что после повреждения / удаления ребер из графа, нет никакой связи между бомбами -
то естьafter damaging, there is no path between any two bombs.
cost of damaging the Edge(u,v) = Edge weight(u,v).
Так,we have to damage those edges, such that the total damaging cost is minimum.
Пример:
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
What i had done?
До сих пор я не нашел эффективного способа :(.
Далее, так как количество узловN
количество ребер точноN-1
и весь граф таков, что существует уникальный путь между любой парой узлов, я пришел к выводу, чтоthe graph is a TREE.
Я пытался изменить алгоритм Крускала, но это мне тоже не помогло.
Спасибо!