> For the complete documentation index, see [llms.txt](https://cai-sen-se.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cai-sen-se.gitbook.io/leetcode/1001-2000/1135.-zui-di-cheng-ben-lian-tong-suo-you-cheng-shi.md).

# 1135.最低成本联通所有城市

#### [付费题](https://leetcode-cn.com/problems/connecting-cities-with-minimum-cost/)

## 一、最小生成树（Kruskal算法）

cost视为边的权值，连通所有城市的最小成本即最小生成树的权值之和

```python
#并查集实现略
class Solution:
    def minimumCost(self, n: int, connections: List[List[int]]) -> int:      
        uf = UnionFind(n+1) # 0号结点不用
        res = 0 #最终成本
        # 将connections按权值排序，然后从小到大遍历
        connections.sort(key = lambda x : x[2])	
        for a, b, w in connections:
            if not uf.isConnected(a, b):	#若ab不连通，则将其加入生成树（即连接）
                uf.union(a, b)
                res += w	#加上权值
        return res if uf.count == 2 else -1	#因为0不用，所有最终连通分量数为2才表示存在最小生成树
```