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完整代碼如下：
```go
package main
import (
"fmt"
"sort"
)
const MAXN = 10010
var edges [][3]int
var esize int
var father [MAXN]int
var size [MAXN]int
var 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代碼如下：
```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++完整代碼如下：
```cpp
#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完整代碼如下：
```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;
}
```
