text: # LeetCode: 1168. 水资源分配优化¶
  
  ## 1、题目描述¶
  
  • 一种是直接在房子内建造水井，成本为 wells[i]
  • 另一种是从另一口井铺设管道引水，数组 pipes 给出了在房子间铺设管道的成本，其中每个 pipes[i] = [house1, house2, cost] 代表用管道将 house1house2 连接在一起的成本。当然，连接是双向的。
  
  输入：n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]
  
  
  
  • $1 <= n <= 10000$
  • $wells.length == n$
  • $0 <= wells[i] <= 10^5$
  • $1 <= pipes.length <= 10000$
  • $1 <= pipes[i][0], pipes[i][1] <= n$
  • $0 <= pipes[i][2] <= 10^5$
  • $pipes[i][0] != pipes[i][1]$
  
  ## 2、解题思路¶
  
  • 添加一个0节点，代表下水道
  • 使用并查集做最小生成树即可
  class DFU:
  def __init__(self, length):
  self.data = list(range(length))
  
  def find(self, x):
  if self.data[x] != x:
  self.data[x] = self.find(self.data[x])
  return self.data[x]
  
  def union(self, x, y):
  xp = self.find(x)
  yp = self.find(y)
  if xp != yp:
  self.data[xp] = yp
  
  def count(self):
  res = 0
  for index, i in enumerate(self.data):
  if index == i:
  res += 1
  return res
  
  class Solution:
  def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:
  queue = []
  for index, well in enumerate(wells):
  queue.append([well, 0, index + 1])
  
  for h1, h2, cost in pipes:
  queue.append([cost, h1, h2])
  ans = 0
  d = DFU(n + 1)
  for cost, h1, h2 in sorted(queue):
  if d.find(h1) == d.find(h2):
  continue
  ans += cost
  d.union(h1, h2)
  return ans