पायथन में एक गांव में जल वितरण का अनुकूलन करें

मान लीजिए किसी गाँव में n घर हैं। हमें सभी घरों में कुएं बनाकर और पाइप बिछाकर पानी की आपूर्ति करनी है। प्रत्येक घर के लिए, हम या तो इसके अंदर एक कुआं बना सकते हैं, भवन की लागत कुएं [i] होगी, या दूसरे कुएं से पानी में पाइप। घरों के बीच पाइप बिछाने की लागत सरणी पाइप द्वारा दी जाती है, जहां प्रत्येक पाइप [i] [हाउस 1, हाउस 2, लागत] एक पाइप का उपयोग करके हाउस 1 और हाउस 2 को एक साथ जोड़ने की लागत का प्रतिनिधित्व करता है। ये कनेक्शन द्विदिश हैं। हमें सभी घरों में पानी की आपूर्ति के लिए न्यूनतम कुल लागत का पता लगाना होगा।

इसलिए, यदि इनपुट n =3, कुओं =[1,2,2], पाइप्स =[[1,2,1], [2,3,1]] जैसा है, तो आउटपुट 3

जैसा कि ऊपर की छवि में पाइप का उपयोग करके घरों को जोड़ने की लागत को दिखाया गया है। सबसे अच्छी रणनीति यह होगी कि पहले घर में लागत 1 के साथ एक कुआं बनाया जाए और दूसरे घरों को लागत 2 से जोड़ा जाए ताकि कुल लागत 3 हो।

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

• फ़ंक्शन ढूंढें () को परिभाषित करें। इसमें एक

  . लगेगा

• अगर माता-पिता [ए] -1 के समान है, तो

  • वापसी एक

• माता-पिता [ए]:=ढूंढें (माता-पिता [ए])

• माता-पिता को लौटाएं[ए]

• एक फ़ंक्शन यूनियन () को परिभाषित करें। इसमें a,b

  . लगेगा

• माता-पिता_ए:=ढूंढें (ए)

• माता-पिता_बी:=ढूंढें (बी)

• अगर parent_a, parent_b के समान है, तो

  • सही लौटें

• माता-पिता [parent_b] :=parent_a

• झूठी वापसी

• मुख्य विधि से निम्न कार्य करें -

• पैरेंट:=आकार n + 1 की सूची बनाएं, इसे -1 से भरें

• काउंटर :=0

• मैं के लिए 0 से कुएं के आकार की सीमा में, ऐसा करें

  • पाइप के अंत में [0, i+1, वेल[i]] डालें

  • काउंटर :=काउंटर + 1

• लागत के आधार पर पाइप की सरणी को क्रमबद्ध करें

• लागत :=0

• पाइप में प्रत्येक i के लिए, करें

  • स्रोत:=मैं[0]

  • गंतव्य:=मैं[1]

  • अस्थायी:=मैं[2]

  • यदि संघ (स्रोत, गंतव्य) गलत है, तो

    • लागत:=लागत + अस्थायी

• वापसी लागत

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

उदाहरण

class Solution(object):
   def find(self, a):
      if self.parent[a] == -1:
         return a
      self.parent[a] = self.find(self.parent[a])
      return self.parent[a]
   def union(self,a,b):
      parent_a = self.find(a)
      parent_b = self.find(b)
      if parent_a == parent_b:
         return True
      self.parent[parent_b] = parent_a
      return False
   def minCostToSupplyWater(self, n, well, pipes):
      self.parent = [-1 for i in range(n+1)]
      counter = 0
      for i in range(len(well)):
         pipes.append([0,i+1,well[i]])
         counter+=1
      pipes = sorted(pipes,key=lambda v:v[2])
      cost = 0
      for i in pipes:
         #print(i)
         source = i[0]
         destination = i[1]
         temp = i[2]
         if not self.union(source,destination):
            cost+=temp
      return cost

ob = Solution()
print(ob.minCostToSupplyWater(3, [1,2,2], [[1,2,1],[2,3,1]]))

इनपुट

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

आउटपुट

1