难度: Hard
Submission
运行时间: 93 ms
内存: 22.3 MB
class Solution:
def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:
'''
初看这个题很难入手，
如果把房子看作点，水井也看作点就很容易理解了。
管道代价是链接点代价，水井代价也是房子链接水井的代价
然后就是最短路径算法了
'''
n=len(wells)
parent=list(range(n+1))#n所房子，1口水井
cnt=[1]*(n+1)
def find(idx:int)->int:
if idx!=parent[idx]:
parent[idx]=find(parent[idx])
return parent[idx]
def getsize(idx:int)->int:
return cnt[find(idx)]
def unite(idx1:int,idx2:int):
a,b=find(idx1),find(idx2)
if a!=b:
if a>b:
a,b=b,a
cnt[a] +=cnt[b]
parent[b]=a
def isconnected(idx1:int,idx2:int)->bool:
return find(idx1)==find(idx2)
for i in range(n):
pipes.append([0,i+1,wells[i]])
pipes.sort(key=lambda p:p[2])
res=0
for x,y,c in pipes:
if isconnected(x,y): continue
res +=c
unite(x,y)
if getsize(0)==n+1:
break
return res
Explain
该题解采用了并查集数据结构来解决最小生成树问题，具体为Kruskal算法的变体。首先，将每个水井视为与每个房子直接相连的特殊节点，将其连接成本作为边的权重。将所有的管道和水井到房子的连接都看作边，并按照成本对这些边进行排序。接下来，使用并查集来逐一检查排序后的边，如果连接的两个节点不在同一集合中，则将这两个节点合并，并将边的成本加到总成本中。通过并查集操作，保证图中不会形成环，最终当所有房子都被连接到水源后（即并查集的根节点包括所有节点），算法结束。
时间复杂度: O((m+n)log(m+n))
空间复杂度: O(m+n)
class Solution:
def minCostToSupplyWater(self, n: int, wells: List[int], pipes: List[List[int]]) -> int:
# 初始化节点数为n + 1（包括虚拟节点0代表所有水井）
n = len(wells)
parent = list(range(n + 1))
cnt = [1] * (n + 1)
# 查找节点的根，并进行路径压缩
def find(idx: int) -> int:
if idx != parent[idx]:
parent[idx] = find(parent[idx])
return parent[idx]
# 获取集合的大小
def getsize(idx: int) -> int:
return cnt[find(idx)]
# 合并两个节点所在的集合
def unite(idx1: int, idx2: int):
a, b = find(idx1), find(idx2)
if a != b:
if a > b:
a, b = b, a
cnt[a] += cnt[b]
parent[b] = a
# 检查两个节点是否已经连接
def isconnected(idx1: int, idx2: int) -> bool:
return find(idx1) == find(idx2)
# 将所有水井作为边添加到管道列表
for i in range(n):
pipes.append([0, i + 1, wells[i]])
# 按成本排序所有边
pipes.sort(key=lambda p: p[2])
res = 0
# 遍历所有边，连接尚未连接的节点，并更新总成本
for x, y, c in pipes:
if isconnected(x, y): continue
res += c
unite(x, y)
# 若所有节点均已连接，则终止循环
if getsize(0) == n + 1:
break
return res
Explore
Kruskal算法是一种贪心算法，其目标是找到图中连接所有节点的最小生成树。通过首先将所有边按成本进行排序，算法可以从最小的边开始选择，确保每次添加的边都是当前可用边中成本最低的，这有助于保证最终生成树的总成本是最低的。这一策略符合贪心算法的选择性标准，确保每步选择都是局部最优的，从而达到全局最优。排序步骤还提高了算法的效率，因为一旦遍历到的边导致所有节点都已连通，算法就可以提前终止，避免了无效的检查。
并查集的路径压缩技术是在执行查找操作时实现的。当调用查找函数以确定某个节点的根节点时，路径压缩技术会确保节点到根节点路径上的所有节点都直接连接到根节点。这通过递归地将节点的父节点设置为其根节点来完成。路径压缩显著提高了并查集的效率，因为它减少了未来操作中路径的长度，从而加快了查找和合并操作的执行速度。长期看，这使得并查集的操作几乎可以在常数时间内完成，极大地提高了数据结构的性能。
在并查集的上下文中，阿克曼函数的反函数α(n)用于描述查找操作的均摊时间复杂度。由于阿克曼函数增长极慢，其反函数α(n)即使在非常大的n值下也增长非常缓慢，通常不会超过4或5。因此，在实际应用中，即使n的值非常大，α(n)的值仍然非常小，可以近似为常数。这意味着并查集操作的时间复杂度可以被视为几乎是常数时间，这对于算法的效率具有极大的影响。