2023-08-04：村里面一共有 n 栋房子
我们希望通过建造水井和铺设管道来为所有房子供水。
对于每个房子 i，我们有两种可选的供水方案：
一种是直接在房子内建造水井
成本为 wells[i - 1] （注意 -1 ，因为 索引从 0 开始 ）
另一种是从另一口井铺设管道引水
数组 pipes 给出了在房子间铺设管道的成本
其中每个 pipes[j] = [house1j, house2j, costj]
代表用管道将 house1j 和 house2j 连接在一起的成本。连接是双向的。
请返回 为所有房子都供水的最低总成本 。
这道题很高频，引起注意，
本身也不难，转化一下变成最小生成树的问题即可。
输入：n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]。
输出：3。
来自小红书、字节跳动。
答案 2023-08-04：
大体过程如下：
1.初始化：
1.1.创建边数组 edges 用于存储管道的信息。
1.2.将每个房子 i 作为一个独立的连通分量，创建并查集的父数组 father[i] 初始化为 i。
1.3.创建每个房子的大小数组 size[i] 初始化为 1。
1.4.创建辅助数组 help 用于路径压缩。
2.构建边数组：
2.1.将每个房子 i 内建造水井的成本 wells[i-1] 加入边数组 edges。
2.2.将每个管道 [house1j, house2j, costj] 的信息加入边数组 edges。
3.对边数组进行排序：
3.1.根据边的成本从小到大对边数组 edges 进行排序。
4.构建并查集：
4.1.调用 build(n) 函数来初始化并查集。
5.最小生成树的构建与计算最低总成本：5.1.初始化 ans = 0，用于记录最低总成本。
5.2.遍历边数组 edges，对于每条边 edges[i]，执行以下步骤：
5.2.1.判断边 edges[i] 的两个节点是否连通（使用并查集中的 find() 函数）：
5.2.1.1.若不连通，则将这两个节点合并（使用并查集中的 union() 函数）。
5.2.1.2.同时累加上该边的成本 edges[i][2] 到总成本 ans 中。
6.返回最低总成本 ans。
总的时间复杂度：O((n+m)log(n+m))，其中 n 是房子数量，m 是管道数量，因为对边数组进行了排序。
总的空间复杂度：O(n+m)，其中 n 是房子数量，m 是管道数量（边的数量）。
go 完整代码如下：
package main
import ( "fmt" "sort")
const MAXN = 10010
var edges [][3]intvar esize intvar father [MAXN]intvar size [MAXN]intvar help [MAXN]int
func build(n int) { for i := 0; i <= n; i++ { father[i] = i size[i] = 1 }}
func find(i int) int { s := 0 for i != father[i] { help[s] = i i = father[i] s++ } for s > 0 { s-- father[help[s]] = i } return i}
func union(i, j int) bool { f1 := find(i) f2 := find(j) if f1 != f2 { if size[f1] >= size[f2] { father[f2] = f1 size[f1] += size[f2] } else { father[f1] = f2 size[f2] += size[f1] } return true } return false}
func minCostToSupplyWater(n int, wells []int, pipes [][]int) int { esize = 0 for i := 0; i < n; i++ { edges = append(edges, [3]int{0, i + 1, wells[i]}) esize++ } for i := 0; i < len(pipes); i++ { edges = append(edges, [3]int{pipes[i][0], pipes[i][1], pipes[i][2]}) esize++ } sort.Slice(edges, func(i, j int) bool { return edges[i][2] < edges[j][2] }) build(n) ans := 0 for i := 0; i < esize; i++ { if union(edges[i][0], edges[i][1]) { ans += edges[i][2] } } return ans}
func main() { n := 3 wells := []int{1, 2, 2} pipes := [][]int{{1, 2, 1}, {2, 3, 1}}
result := minCostToSupplyWater(n, wells, pipes) fmt.Println(result)}
复制代码
rust 代码如下：
const MAXN: i32 = 10010;
static mut EDGES: [[i32; 3]; (MAXN << 1) as usize] = [[0; 3]; (MAXN << 1) as usize];static mut ESIZE: i32 = 0;
static mut FATHER: [i32; MAXN as usize] = [0; MAXN as usize];static mut SIZE: [i32; MAXN as usize] = [0; MAXN as usize];static mut HELP: [i32; MAXN as usize] = [0; MAXN as usize];
fn build(n: i32) { for i in 0..=n { unsafe { FATHER[i as usize] = i; SIZE[i as usize] = 1; } }}
fn find(i: i32) -> i32 { let mut s = 0; unsafe { let mut index = i; while index != FATHER[index as usize] { HELP[s] = index; index = FATHER[index as usize]; s += 1; } while s > 0 { s -= 1; FATHER[HELP[s] as usize] = index; } return index; }}
fn union(i: i32, j: i32) -> bool { let f1 = find(i); let f2 = find(j); unsafe { if f1 != f2 { if SIZE[f1 as usize] >= SIZE[f2 as usize] { FATHER[f2 as usize] = f1; SIZE[f1 as usize] += SIZE[f2 as usize]; } else { FATHER[f1 as usize] = f2; SIZE[f2 as usize] += SIZE[f1 as usize]; } return true; } else { return false; } }}
fn min_cost_to_supply_water(n: i32, wells: &[i32], pipes: &[[i32; 3]]) -> i32 { unsafe { ESIZE = 0; for i in 0..n { EDGES[ESIZE as usize][0] = 0; EDGES[ESIZE as usize][1] = i + 1; EDGES[ESIZE as usize][2] = wells[i as usize]; ESIZE += 1; } for i in 0..pipes.len() { EDGES[ESIZE as usize][0] = pipes[i][0] as i32; EDGES[ESIZE as usize][1] = pipes[i][1] as i32; EDGES[ESIZE as usize][2] = pipes[i][2]; ESIZE += 1; } EDGES[0..ESIZE as usize].sort_by(|a, b| a[2].cmp(&b[2])); build(n); let mut ans = 0; for i in 0..ESIZE { if union(EDGES[i as usize][0], EDGES[i as usize][1]) { ans += EDGES[i as usize][2]; } } return ans; }}
fn main() { let n = 3; let wells = [1, 2, 2]; let pipes = [[1, 2, 1], [2, 3, 1]]; let result = min_cost_to_supply_water(n, &wells, &pipes); println!("Minimum cost to supply water: {}", result);}
复制代码
c++完整代码如下：
#include <iostream>#include <vector>#include <array>#include <algorithm>using namespace std;
const int MAXN = 10010;vector<array<int, 3>> edges;int father[MAXN];int size2[MAXN];int help[MAXN];
void build(int n) { for (int i = 0; i <= n; i++) { father[i] = i; size2[i] = 1; }}
int find(int i) { int s = 0; while (i != father[i]) { help[s++] = i; i = father[i]; } while (s > 0) { father[help[--s]] = i; } return i;}
bool unionSet(int i, int j) { int f1 = find(i); int f2 = find(j); if (f1 != f2) { if (size2[f1] >= size2[f2]) { father[f2] = f1; size2[f1] += size2[f2]; } else { father[f1] = f2; size2[f2] += size2[f1]; } return true; } else { return false; }}
int minCostToSupplyWater(int n, vector<int>& wells, vector<vector<int>>& pipes) { edges.clear(); for (int i = 0; i < n; i++) { edges.push_back({ 0, i + 1, wells[i] }); } for (int i = 0; i < pipes.size(); i++) { edges.push_back({ pipes[i][0], pipes[i][1], pipes[i][2] }); } sort(edges.begin(), edges.end(), [](const array<int, 3>& a, const array<int, 3>& b) { return a[2] < b[2]; }); build(n); int ans = 0; for (int i = 0; i < edges.size(); i++) { if (unionSet(edges[i][0], edges[i][1])) { ans += edges[i][2]; } } return ans;}
int main() { int n = 3; vector<int> wells = { 1, 2, 2 }; vector<vector<int>> pipes = { {1, 2, 1}, {2, 3, 1} }; int result = minCostToSupplyWater(n, wells, pipes); cout << "Minimum cost to supply water: " << result << endl; return 0;}
复制代码
c 完整代码如下：
#include <stdio.h>#include <stdlib.h>
#define MAXN 10010
int edges[MAXN << 1][3];int esize;int father[MAXN];int size[MAXN];int help[MAXN];
void build(int n) { for (int i = 0; i <= n; i++) { father[i] = i; size[i] = 1; }}
int find(int i) { int s = 0; while (i != father[i]) { help[s++] = i; i = father[i]; } while (s > 0) { father[help[--s]] = i; } return i;}
int union2(int i, int j) { int f1 = find(i); int f2 = find(j); if (f1 != f2) { if (size[f1] >= size[f2]) { father[f2] = f1; size[f1] += size[f2]; } else { father[f1] = f2; size[f2] += size[f1]; } return 1; } else { return 0; }}
int minCostToSupplyWater(int n, int wells[], int pipes[][3], int pipesSize) { esize = 0; for (int i = 0; i < n; i++, esize++) { edges[esize][0] = 0; edges[esize][1] = i + 1; edges[esize][2] = wells[i]; } for (int i = 0; i < pipesSize; i++, esize++) { edges[esize][0] = pipes[i][0]; edges[esize][1] = pipes[i][1]; edges[esize][2] = pipes[i][2]; }
// Sort edges based on the third column (weights) for (int i = 0; i < esize; i++) { for (int j = 0; j < esize - 1; j++) { if (edges[j][2] > edges[j + 1][2]) { int temp[3]; temp[0] = edges[j][0]; temp[1] = edges[j][1]; temp[2] = edges[j][2]; edges[j][0] = edges[j + 1][0]; edges[j][1] = edges[j + 1][1]; edges[j][2] = edges[j + 1][2]; edges[j + 1][0] = temp[0]; edges[j + 1][1] = temp[1]; edges[j + 1][2] = temp[2]; } } }
build(n); int ans = 0; for (int i = 0; i < esize; i++) { if (union2(edges[i][0], edges[i][1])) { ans += edges[i][2]; } } return ans;}
int main() { int n = 3; int wells[] = { 1, 2, 2 }; int pipes[][3] = { {1, 2, 1}, {2, 3, 1} }; int pipesSize = sizeof(pipes) / sizeof(pipes[0]);
int result = minCostToSupplyWater(n, wells, pipes, pipesSize); printf("Minimum cost to supply water: %d\n", result);
return 0;}
复制代码
评论