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]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代码如下：

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;
}

本作品采用《CC 协议》，转载必须注明作者和本文链接