Tối ưu phân phối nước trong làng với Python

Cho n ngôi nhà trong làng. Cần cấp nước bằng cách khoan giếng hoặc lắp ống. Mỗi nhà i có thể khoan giếng với chi phí wells[i], hoặc kéo ống từ giếng khác. Chi phí lắp ống giữa các nhà cho bởi mảng pipes, mỗi pipes[i] = [house1, house2, cost]. Kết nối hai chiều. Tìm chi phí tối thiểu cấp nước cho tất cả nhà.

Ví dụ: n=3, wells=[1,2,2], pipes=[[1,2,1],[2,3,1]] → kết quả 3. Khoan giếng ở nhà 1 (chi phí 1), nối nhà 2,3 vào (chi phí 2) → tổng 3.

Giải thuật (Kruskal + Union Find)

• Coi việc khoan giếng như nối từ "siêu nút" 0 đến nhà i với chi phí wells[i]
• Gộp tất cả cạnh (pipes + giếng) và sắp xếp theo chi phí
• Duyệt cạnh theo thứ tự chi phí tăng, dùng Union-Find tránh chu trình
• Tổng chi phí các cạnh được chọn là kết quả

Ví dụ triển khai

class Solution:
    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]]))

Đầu vào

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

Đầu ra

3