Minimalne szkodliwe koszty na wykresie
Otrzymujemy wykres G (V, E) z N węzłami (ponumerowane od 0 do N-1) i dokładnie (N-1)dwukierunkowe krawędzie.
Każda krawędź na wykresie makoszt dodatni C (u, v)(Waga krawędzi).
Cały wykres jest taki, żeistnieje unikalna ścieżka między dowolną parą węzłów.
Otrzymujemy także listęL numeru węzła, na którym umieszczona jest bomba.
Naszym celem jestuszkodzić / usunąć krawędź z wykresu takiego, że po uszkodzeniu / usunięciu krawędzi z wykresu nie ma połączenia między Bombami -
to jestpo uszkodzeniu nie ma żadnej ścieżki między dwiema bombami.
Thekoszt uszkodzenia Edge (u, v) = Waga krawędzi (u, v).
Więc,musimy uszkodzić te krawędzie, aby całkowity koszt uszkodzenia był minimalny.
Przykład:
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
Co zrobiłem?
Do tej pory nie znalazłem żadnego skutecznego sposobu :(.
Dalej, jak liczba węzłów jestN
, liczba krawędzi jest dokładnie takaN-1
a cały wykres jest taki, że istnieje wyjątkowa ścieżka między dowolną parą węzłówwykres jest aDRZEWO.
Próbowałem zmodyfikować algorytm Kruskala, ale to też mi nie pomogło.
Dzięki!