N 個のノード (0 から N-1 までの番号) と正確に (N-1) 個の双方向 Edgesを持つグラフ G(V,E) が与えられます。
グラフの各エッジには正のコスト C(u,v) (エッジの重み) があります。
グラフ全体は、ノードの任意のペア間に一意のパスがあるようなものです。
また、爆弾が配置されるノード番号のリストLも与えられます。
私たちの目的は、グラフからエッジを損傷/除去した後、爆弾間の接続がなくなるように、グラフからエッジを損傷/除去することです --
つまり、ダメージを与えた後、2 つの爆弾の間にパスがありません。
Edge(u,v) = Edge weight(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であるため、エッジの数は正確であり、グラフ全体はノードの任意のペア間に一意のパスがあるようなものであり、グラフはTREEN-1であるという結論を得ました。
Kruskal アルゴリズムを変更しようとしましたが、それも役に立ちませんでした。
ありがとう！