2023-08-04：村里面一共有 n 棟房子 我們希望通過建造水井和鋪設(shè)管道來為所有房子供水
2023-08-04：村里面一共有 n 棟房子
我們希望通過建造水井和鋪設(shè)管道來為所有房子供水。
對于每個房子 i，我們有兩種可選的供水方案：
一種是直接在房子內(nèi)建造水井
成本為 wells[i - 1] （注意 -1 ，因為 索引從0開始 ）
另一種是從另一口井鋪設(shè)管道引水
數(shù)組 pipes 給出了在房子間鋪設(shè)管道的成本
其中每個 pipes[j] = [house1j, house2j, costj]
代表用管道將 house1j 和 house2j連接在一起的成本。連接是雙向的。
請返回 為所有房子都供水的最低總成本 。
這道題很高頻，引起注意，
本身也不難，轉(zhuǎn)化一下變成最小生成樹的問題即可。
輸入：n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]]。
輸出：3。
來自小紅書、字節(jié)跳動。
答案2023-08-04：
# 大體過程如下：
1.初始化：
1.1.創(chuàng)建邊數(shù)組 edges 用于存儲管道的信息。
1.2.將每個房子 i 作為一個獨立的連通分量，創(chuàng)建并查集的父數(shù)組 father[i] 初始化為 i。
1.3.創(chuàng)建每個房子的大小數(shù)組 size[i] 初始化為 1。
1.4.創(chuàng)建輔助數(shù)組 help 用于路徑壓縮。
2.構(gòu)建邊數(shù)組：
2.1.將每個房子 i 內(nèi)建造水井的成本 wells[i-1] 加入邊數(shù)組 edges。
2.2.將每個管道 [house1j, house2j, costj] 的信息加入邊數(shù)組 edges。
3.對邊數(shù)組進行排序：
3.1.根據(jù)邊的成本從小到大對邊數(shù)組 edges 進行排序。
4.構(gòu)建并查集：
4.1.調(diào)用 build(n) 函數(shù)來初始化并查集。
5.最小生成樹的構(gòu)建與計算最低總成本：
5.1.初始化 ans = 0，用于記錄最低總成本。
5.2.遍歷邊數(shù)組 edges，對于每條邊 edges[i]，執(zhí)行以下步驟：
5.2.1.判斷邊 edges[i] 的兩個節(jié)點是否連通（使用并查集中的 find() 函數(shù)）：
5.2.1.1.若不連通，則將這兩個節(jié)點合并（使用并查集中的 union() 函數(shù)）。
5.2.1.2.同時累加上該邊的成本 edges[i][2] 到總成本 ans 中。
6.返回最低總成本 ans。
總的時間復雜度：O((n+m)log(n+m))，其中 n 是房子數(shù)量，m 是管道數(shù)量，因為對邊數(shù)組進行了排序。
總的空間復雜度：O(n+m)，其中 n 是房子數(shù)量，m 是管道數(shù)量（邊的數(shù)量）。
# 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;
}
```
