# 1168. Optimize Water Distribution in a Village
###### tags: `Leetcode` `Hard` `Union Find` `Minimum Spanning Tree`
Link: https://leetcode.com/problems/optimize-water-distribution-in-a-village/description/
## 思路
思路参考[这里](https://leetcode.com/problems/optimize-water-distribution-in-a-village/solutions/365853/c-python-java-hidden-well-in-house-0/)
把题目理解成 我们不能build任何wells 有且只有一个hidden wells在house ```0```(也可以想成是river 也就是wells的水源)
那么我们需要用pipes将所有的house和house ```0```连在一起
house ```i```和house ```0```之间build pipes的cost就是```wells[i-1]```
因此我们需要在graph上找到一个MST 就是答案
## Code

class Solution:
    def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:
        fa = {i:i for i in range(n+1)}
        
        def find(a):
            if a != fa[a]:
                fa[a] = find(fa[a])
            return fa[a]
        
        w = [[c, 0, i] for i, c in enumerate(wells, 1)]
        p = [[c, i, j] for i, j, c in pipes]
        result = 0

        for c, x, y in sorted(w+p):
            a = find(x)
            b = find(y)
            if a!=b:
                fa[a] = b
                result += c
                n -= 1
            if n==0: 
                return result