ধরা যাক একটি গ্রামে n সংখ্যক বাড়ি আছে। সব বাড়িতে জল সরবরাহ করতে হবে কূপ (well) খনন করে এবং পাইপ বिछিয়ে। প্রতিটি বাড়ি i-তে কূপ খনন করলে খরচ হবে wells[i], অথবা অন্য কূপ থেকে পাইপ দিয়ে জল আনতে হবে। পাইপ বिछানোর খরচ pipes অ্যারেতে দেওয়া আছে, যেখানে pipes[i] = [house1, house2, cost] বাড়ি দুটি সংযুক্ত করার খরচ। সংযোগ দ্বিমুখী। সব বাড়িতে জল সরবরাহের ন্যূনতম মোট খরচ বের করতে হবে।
যেমন, n = 3, wells = [1, 2, 2], pipes = [[1,2,1], [2,3,1]] হলে আউটপুট হবে ৩।
চিত্রে পাইপ সংযোগের খরচ দেখানো আছে। সেরা কৌশল: প্রথম বাড়িতে কূপ খনন (খরচ ১) এবং বাকি দুটি বাড়ি সেটির সাথে সংযুক্ত (খরচ ২) — মোট খরচ ৩।
find(a) ফাংশন: প্যারেন্ট খুঁজে বের করে পাথ কম্প্রেশন সহ।
union(a, b) ফাংশন: দুটি নোড একসাথে যোজন করলে সাইকেল আছে কিনা চেক করে।
প্রতিটি বাড়ির জন্য কূপ খননকে একটি ভার্চুয়াল নোড ০ থেকে সংযোগ হিসেবে বিবেচনা করা হয় (cost = wells[i])।
সকল এজ (পাইপ + কূপ) খরচ অনুযায়ী সর্ট করা হয়।
Kruskal's MST অ্যালগরিদম প্রয়োগ করে ন্যূনতম খরচ বের করা হয়।
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 _ in range(n + 1)]
for i in range(len(well)):
pipes.append([0, i + 1, well[i]])
pipes = sorted(pipes, key=lambda v: v[2])
cost = 0
for i in pipes:
source, destination, temp = i[0], i[1], 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]]
3
