न्यूनतम लागत का पता लगाने के लिए कार्यक्रम ताकि नागरिकों की पायथन में बाजार तक पहुंच हो

मान लीजिए, शहरों की संख्या n है और शहरों को जोड़ने वाली m सड़कें हैं। लोगों के नागरिकों को ऐसे बाजारों की जरूरत है जहां वे अपना सामान खरीद सकें। अब, शहरों में कोई बाजार नहीं है, और शहरों के बीच सड़कें निर्माणाधीन हैं। दो शहरों के बीच एक दो-तरफा सड़क बनाई जा सकती है यदि (i) शहर में एक बाजार हो; (ii) शहरों में सड़क मार्ग से जाया जा सकता है जहां बाजार है। एक सड़क बनाने की लागत x है, और बाजार बनाने की लागत y है और उन्हें दिया गया है। हमें प्रत्येक शहर के नागरिकों को बाजारों तक पहुंच प्रदान करने के लिए न्यूनतम लागत का पता लगाना होगा। सरणी 'शहरों' में उन शहरों के बारे में जानकारी होती है जिनके बारे में शहरों को सड़क मार्ग से जोड़ा जा सकता है।

इसलिए, यदि इनपुट n =4, m =3, x =1, y =2, शहर =[[1, 2], [2, 3], [3, 4]] जैसा है, तो आउटपुट होगा 4.

यहां, हम चार शहर 1, 2, 3 और 4 देख सकते हैं। यदि एक शहर 1 में एक बाजार बनाया जाता है और (1, 4) और (1,3) के बीच दो और सड़कें बनाई जाती हैं, तो कुल लागत 2 + 1 होगी। + 1 =4. यह न्यूनतम लागत है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• यदि x <=y, तो
  • वापसी n * x
• अन्यथा,
  • adj_list :=तत्वों के रूप में सूचियों वाला नक्शा
  • शहरों के प्रत्येक शहर के लिए, करें
    • शहर1:=शहर[0]
    • शहर2:=शहर[1]
    • adj_list[city1] के अंत में City2 डालें
    • adj_list[city2] के अंत में City1 डालें
  • अस्थायी:=आकार की एक नई सूची (n + 1) मूल्य के साथ आरंभिक सत्य
  • मान :=0
  • dq :=एक डबल एंडेड कतार
  • 1 से n + 1 तक के वक्र के लिए
    • यदि अस्थायी [cur] शून्य नहीं है, तो
      • मान :=मान + x
      • dq के सबसे दाहिने सिरे पर cur डालें
      • अस्थायी[cur] :=गलत
      • जबकि dq खाली नहीं है, करें
      • प्रत्येक के लिए मैं adj_list[dq का सबसे बायां तत्व निकाला गया], करता हूं
        • यदि अस्थायी [i] शून्य नहीं है, तो
          • dq के सबसे दाहिने सिरे पर i डालें
          • अस्थायी[i] :=गलत
          • मान :=मान + y
  • वापसी मूल्य

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

from collections import defaultdict, deque
def solve(n, m, x, y, cities):
   if x <= y:
      return n * x
   else:
      adj_list = defaultdict(list)
      for city in cities:
         city1 = city[0]
         city2 = city[1]
         adj_list[city1].append(city2)
         adj_list[city2].append(city1)
      temp = [True] * (n + 1)
      value = 0
      dq = deque()
      for cur in range(1, n + 1):
         if temp[cur]:
            value += x
            dq.append(cur)
            temp[cur] = False
            while dq:
               for i in adj_list[dq.popleft()]:
                  if temp[i]:
                     dq.append(i)
                     temp[i] = False
                     value += y
      return value

print(solve(4, 3, 1, 2, [[1, 2], [2, 3], [3, 4]]))

इनपुट

4, 3, 2, 1, [[1, 2], [2, 3], [3, 4]]

आउटपुट

4