資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學使用Python最佳化鄉村水資源分配
假設一個村莊有n戶人家。我們需要透過建造水井和鋪設管道為所有房屋供水。對於每戶人家i，我們可以選擇在其內部建造一口井，建造成本為wells[i]，或者從另一口水井向其鋪設管道。房屋之間鋪設管道的成本由陣列pipes給出，其中每個pipes[i]為[house1, house2, cost]，表示連線house1和house2的成本。這些連線是雙向的。我們需要找到為所有房屋供水的最小總成本。
因此，如果輸入類似於n = 3，wells = [1,2,2]，pipes = [[1,2,1],[2,3,1]]，則輸出將為3
如上圖所示，顯示了使用管道連線房屋的成本。最佳策略是在第一戶人家建造一口井，成本為1，並將其他房屋以成本2連線到它，因此總成本為3。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式find()。這將接收一個
如果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
對於從0到well大小的範圍內的i，執行以下操作：
在pipes的末尾插入[0, i+1, well[i]]
counter := counter + 1
根據成本對pipes陣列進行排序
cost := 0
對於pipes中的每個i，執行以下操作：
source := i[0]
destination := i[1]
temp := i[2]
如果union(source,destination)為false，則
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: #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
582 次瀏覽
