में न्यूनतम हानिकारक लागत हम एन नोड्स के साथ एक ग्राफ जी (वी, ई) और वास्तव में (एन 1) (0 से N-1 के लिए क्रमिक) दो तरह किनारों दिया जाता है।ग्राफ
ग्राफ़ में प्रत्येक किनारे में सकारात्मक लागत सी (यू, वी) (एज वजन) है।
पूरे ग्राफ ऐसे वहाँ नोड्स के किसी भी जोड़ी के बीच एक अनूठा रास्ता है।
हमें नोड संख्या की सूची एल भी दी गई है, जिस पर बम रखा गया है।
हमारा उद्देश्य क्षति के लिए है/ग्राफ से इस तरह के किनारे निकालने के लिए, हानिकारक के बाद/ग्राफ से किनारों को हटाने, वहाँ बम के बीच कोई संबंध नहीं है कि -
कि हानिकारक के बाद है , किसी भी दो बम के बीच कोई रास्ता नहीं है।
एज (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 है और पूरे ग्राफ इस तरह वहाँ एक अनोखा रास्ता है नोड्स के किसी भी जोड़ी के बीच, मैं एक निष्कर्ष यह है कि ग्राफ एक वृक्ष है मिला है।
मैं Kruskal एल्गोरिथ्म संशोधित करने की कोशिश की लेकिन है कि या तो मेरी मदद नहीं की।
धन्यवाद!
मुझे विश्वास है कि एक लालची दृष्टिकोण (प्रत्येक पथ में सबसे निचले चरम को हटा दें) के पास एक पेड़ में एक मौका है, लेकिन मुझे अभी तक इसके बारे में निश्चित नहीं है: \ इसके अलावा: आप एक कुशल दृष्टिकोण के रूप में क्या पाएंगे? – amit
@ अमित, अब तक मैं इसे हल करने के लिए कोई कुशल विधि नहीं ढूंढ पा रहा हूं। नोड्स = 100,000 की बाधा संख्या, जिसका मतलब कुल किनारों = 100,000-1 है। तो ओ (एन लॉग एन) एल्गोरिदम आसान और कुशल होगा। –
@All :: बाधाओं को एक संपादन के रूप में जोड़ा गया। –