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
explanation: The provided text is a detailed problem description and solution for a LeetCode problem titled "水资源分配优化" (Optimal Water Distribution). The problem involves optimizing the cost of supplying water to houses by either building wells or laying pipes. The text includes the problem statement, constraints, and a Python solution using a Disjoint Set Union (DSU) or Union-Find data structure to find the minimum cost.
  
  The text does not contain a direct question or a question-and-answer format. It is primarily a problem description and a solution.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: # 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
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The provided text is a detailed problem description and solution for a LeetCode problem titled "水资源分配优化" (Optimal Water Distribution). The problem involves optimizing the cost of supplying water to houses by either building wells or laying pipes. The text includes the problem statement, constraints, and a Python solution using a Disjoint Set Union (DSU) or Union-Find data structure to find the minimum cost.
  
  The text does not contain a direct question or a question-and-answer format. It is primarily a problem description and a solution.
  
  Label: no-question