मान लीजिए एक गांव में n घर हैं। हमें कुएं बनाकर और पाइप बिछाकर सभी घरों में पानी की आपूर्ति करनी है। प्रत्येक घर i के लिए, हम या तो उसके अंदर एक कुआं बना सकते हैं, जिसकी लागत wells[i] होगी, या किसी अन्य कुएं से पाइप के माध्यम से पानी ला सकते हैं। घरों के बीच पाइप बिछाने की लागत सरणी pipes द्वारा दी जाती है, जहां प्रत्येक pipes[i] = [house1, house2, cost] घर 1 और घर 2 को पाइप का उपयोग करके जोड़ने की लागत दर्शाता है। ये कनेक्शन द्विदिश हैं। हमें सभी घरों में पानी की आपूर्ति करने की न्यूनतम कुल लागत ढूंढनी है।
इसलिए, यदि इनपुट इस तरह है n = 3, wells = [1, 2, 2], pipes = [[1, 2, 1], [2, 3, 1]], तो आउटपुट 3 होगा।
ऊपर की छवि दिखाती है कि पाइप का उपयोग करके घरों को जोड़ने की लागत क्या है। सबसे अच्छी रणनीति पहले घर में 1 की लागत से कुआं बनाना और अन्य घरों को इससे 2 की लागत से जोड़ना होगा, इसलिए कुल लागत 3 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
find() फ़ंक्शन परिभाषित करें। यह a लेगा
यदि parent[a], -1 के समान है, तो
a लौटाएं
parent[a] := find(parent[a])
parent[a] लौटाएं
union() फ़ंक्शन परिभाषित करें। यह a, b लेगा
parent_a := find(a)
parent_b := find(b)
यदि parent_a, parent_b के समान है, तो
True लौटाएं
parent[parent_b] := parent_a
False लौटाएं
मुख्य मेथड से निम्नलिखित करें -
parent := n + 1 आकार की एक सूची बनाएं, इसे -1 से भरें
counter := 0
i को 0 से well के आकार तक की रेंज में, करें
[0, i+1, well[i]] को pipes के अंत में सम्मिलित करें
counter := counter + 1
पाइप सरणी को लागत के आधार पर क्रमबद्ध करें
cost := 0
पाइप में प्रत्येक i के लिए, करें
source := i[0]
destination := i[1]
temp := i[2]
यदि union(source, destination) गलत है, तो
cost := cost + temp
cost लौटाएं
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
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: 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]]
आउटपुट
3
