代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
村里面一共有 n 栋房子。我们希望通过建造水井和铺设管道来为所有房子供水。
对于每个房子 i，我们有两种可选的供水方案：一种是直接在房子内建造水井，成本为 wells[i - 1] （注意 -1 ，因为 索引从0开始 ）；另一种是从另一口井铺设管道引水，数组 pipes 给出了在房子间铺设管道的成本，其中每个 pipes[j] = [house1j, house2j, costj] 代表用管道将 house1j 和 house2j连接在一起的成本。连接是双向的。
请返回 为所有房子都供水的最低总成本 。
示例 1：
输入：n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]] 输出：3 解释： 上图展示了铺设管道连接房屋的成本。 最好的策略是在第一个房子里建造水井（成本为 1），然后将其他房子铺设管道连起来（成本为 2），所以总成本为 3。
示例 2：
输入：n = 2, wells = [1,1], pipes = [[1,2,1]] 输出：2 解释：我们可以用以下三种方法中的一种来提供低成本的水: 选项1: 在1号房子里面建一口井，成本为1 在房子2内建造井，成本为1 总成本是2。 选项2: 在1号房子里面建一口井，成本为1 -花费1连接房子2和房子1。 总成本是2。 选项3: 在房子2内建造井，成本为1 -花费1连接房子1和房子2。 总成本是2。 注意，我们可以用cost 1或cost 2连接房子1和房子2，但我们总是选择最便宜的选项。
提示：
2 <= n <= 104wells.length == n0 <= wells[i] <= 1051 <= pipes.length <= 104pipes[j].length == 31 <= house1j, house2j <= n0 <= costj <= 105house1j != house2j最小生成树问题。
方法一：Kruskal 算法
对于本题，可以将节点 0 视为水库，水库到房子间的成本等于房子内建造水井的成本。因此此题可以转换为最小生成树问题。
class Solution:
def minCostToSupplyWater(
self, n: int, wells: List[int], pipes: List[List[int]]
) -> int:
for i, w in enumerate(wells):
pipes.append([0, i + 1, w])
pipes.sort(key=lambda x: x[2])
p = list(range(n + 1))
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
res = 0
for u, v, w in pipes:
if find(u) == find(v):
continue
p[find(u)] = find(v)
res += w
n -= 1
if n == 0:
break
return res
class Solution {
private int[] p;
public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
int[][] all = new int[pipes.length + n][3];
int idx = 0;
for (int[] pipe : pipes) {
all[idx++] = pipe;
}
for (int j = 0; j < n; ++j) {
all[idx++] = new int[] {0, j + 1, wells[j]};
}
p = new int[n + 1];
for (int i = 0; i < p.length; ++i) {
p[i] = i;
}
Arrays.sort(all, Comparator.comparingInt(a -> a[2]));
int res = 0;
for (int[] e : all) {
if (find(e[0]) == find(e[1])) {
continue;
}
p[find(e[0])] = find(e[1]);
res += e[2];
--n;
if (n == 0) {
break;
}
}
return res;
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}
class Solution {
public:
vector<int> p;
int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) {
p.resize(n + 1);
for (int i = 0; i < p.size(); ++i) p[i] = i;
for (int i = 0; i < n; ++i) pipes.push_back({0, i + 1, wells[i]});
sort(pipes.begin(), pipes.end(), [](const auto& a, const auto& b) {
return a[2] < b[2];
});
int res = 0;
for (auto e : pipes) {
if (find(e[0]) == find(e[1])) continue;
p[find(e[0])] = find(e[1]);
res += e[2];
--n;
if (n == 0) break;
}
return res;
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
};
var p []int
func minCostToSupplyWater(n int, wells []int, pipes [][]int) int {
p = make([]int, n+1)
for i := 0; i < len(p); i++ {
p[i] = i
}
for i, w := range wells {
pipes = append(pipes, []int{0, i + 1, w})
}
sort.Slice(pipes, func(i, j int) bool {
return pipes[i][2] < pipes[j][2]
})
res := 0
for _, e := range pipes {
if find(e[0]) == find(e[1]) {
continue
}
p[find(e[0])] = find(e[1])
res += e[2]
n--
if n == 0 {
break
}
}
return res
}
func find(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手
