পাইথনের একটি গ্রামে জল বন্টন অপ্টিমাইজ করুন

ধরুন একটি গ্রামে n বাড়ি আছে। কূপ নির্মাণ ও পাইপ বিছিয়ে সব বাড়িতে পানি সরবরাহ করতে হয়। প্রতিটি বাড়ির জন্য, আমরা হয় তার ভিতরে একটি কূপ নির্মাণ করতে পারি, নির্মাণের খরচ হবে কূপ[i], অথবা অন্য একটি কূপ থেকে পানিতে পাইপ। বাড়ির মধ্যে পাইপ স্থাপনের খরচ অ্যারে পাইপ দ্বারা দেওয়া হয়, যেখানে প্রতিটি পাইপ[i] হল [house1, house2, cost] একটি পাইপ ব্যবহার করে house1 এবং house2 কে একসাথে সংযুক্ত করার খরচ উপস্থাপন করে। এই সংযোগগুলি দ্বিমুখী। সমস্ত বাড়িতে জল সরবরাহ করার জন্য আমাদের সর্বনিম্ন মোট খরচ খুঁজে বের করতে হবে৷

সুতরাং, যদি ইনপুট n =3, ওয়েলস =[1,2,2], পাইপ =[[1,2,1],[2,3,1]] এর মত হয়, তাহলে আউটপুট হবে 3

উপরের চিত্র থেকে পাইপ ব্যবহার করে ঘর সংযোগের খরচ দেখায়। সর্বোত্তম কৌশলটি হবে প্রথম বাড়িতে একটি কূপ 1 খরচ দিয়ে তৈরি করা এবং অন্য বাড়িগুলিকে 2 খরচ দিয়ে সংযুক্ত করা যাতে মোট খরচ হয় 3৷

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি ফাংশন খুঁজুন() সংজ্ঞায়িত করুন। এটি একটি

  লাগবে৷

• যদি অভিভাবক[a] -1 এর মত হয়, তাহলে

  • একটি ফেরত দিন

• পিতামাতা[a] :=খুঁজুন(পিতা[ক])

• ফেরত অভিভাবক[a]

• একটি ফাংশন ইউনিয়ন () সংজ্ঞায়িত করুন। এটি a,b

  লাগবে

• parent_a :=খুঁজুন(a)

• parent_b :=খুঁজুন(b)

• যদি parent_a হয় parent_b এর মতো, তাহলে

  • রিটার্ন ট্রু

• পিতামাতা[পিতা_বি] :=পিতামাতা_একটি

• রিটার্ন ফলস

• মূল পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• parent :=n + 1 আকারের একটি তালিকা তৈরি করুন, এটি -1 দিয়ে পূরণ করুন

• কাউন্টার :=0

• আমি 0 থেকে কূপের আকারের মধ্যে, কর

  • পাইপের শেষে [0, i+1, ভাল[i]] প্রবেশ করান

  • কাউন্টার :=কাউন্টার + 1

• খরচের উপর ভিত্তি করে পাইপ অ্যারে সাজান

• খরচ :=0

• প্রতিটি i ইন পাইপের জন্য, করুন

  • উৎস :=i[0]

  • গন্তব্য :=i[1]

  • temp :=i[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