您现在的位置是：首页 >其他 >【2024年华为OD机试】 (A卷,200分)- 最优高铁城市修建方案（JavaScript&Java & Python&C/C++）网站首页其他

一、问题描述

高铁城市圈最低成本修建问题

题目描述

高铁城市圈对人们的出行、经济的拉动效果明显。每年都会规划新的高铁城市圈建设。给定城市数量、可建设高铁的两城市间的修建成本列表、以及结合城市商业价值会固定建设的两城市建高铁。请你设计算法，达到修建城市高铁的最低成本。注意，需要满足城市圈内城市间两两互联可达（通过其他城市中转可达也属于满足条件）。

输入描述

输入信息包括：

1. 第一行，包含此城市圈中城市的数量、可建设高铁的两城市间修建成本列表数量、必建高铁的城市列表。三个数字用空格间隔。
2. 可建设高铁的两城市间的修建成本列表，为多行输入数据，格式为3个数字，用空格分隔，长度不超过1000。
3. 固定要修建的高铁城市列表，是上面参数2的子集，可能为多行，每行输入为2个数字，以空格分隔。

城市id从1开始编号，建设成本的取值为正整数，取值范围均不会超过1000。

输出描述

修建城市圈高铁的最低成本，正整数。如果城市圈内存在两城市之间无法互联，则返回-1。

用例

输入1

3 3 0
1 2 10
1 3 100
2 3 50

输出1

60

说明1

城市圈数量为3，表示城市id分别为1,2,3。满足修建成本最低，只需要建设城市1，2间，城市2，3间的高铁即可，城市1，3之间可通过城市2中转来互联。这样最低修建成本就是60。

输入2

3 3 1
1 2 10
1 3 100
2 3 50
1 3

输出2

110

说明2

城市圈数量为3，表示城市id分别为1，2，3。因为城市1，3间的高铁必须修建，在满足互联的条件下，再增加修建城市1，2间的高铁即可，最低成本为110。

题目解析

本题是求解最小生成树的变种题。在了解最小生成树概念前，我们需要先了解生成树的概念。

生成树概念

在无向连通图中，生成树是指包含了全部顶点的极小连通子图。生成树包含原图全部的n个顶点和n-1条边。（注意，边的数量一定是n-1）

生成树最重要的两个特性就是：

1. 包含所有顶点
2. 无环

最小生成树

最小生成树指的是，生成树中n-1条边的权重值之和最小。有两种算法可以准确地找出一个无向连通图的最小生成树：Prim算法和Kruskal算法。

Prim算法

Prim算法是基于顶点找最小生成树。步骤如下：

1. 选择无向连通图中的任意一个顶点作为起始点。
2. 从起始点出发，选择权重最小的边，将两个顶点相连。
3. 将已连接的顶点看成一个整体，继续找这个整体出发的所有边里面的最小的。
4. 重复上述步骤，直到所有顶点都被连接。

Kruskal算法

Kruskal算法是基于边找最小生成树。步骤如下：

1. 将所有的边按照权重值升序排序。
2. 依次选择权重最小的边，如果加入这条边不会形成环，则加入。
3. 重复上述步骤，直到所有顶点都被连接。

并查集

判断环的存在是实现Prim算法和Kruskal算法的关键点。生成树就是一个连通分量，初始时，生成树这个连通分量只有一个顶点（Prim），或者两个顶点（Kruskal），后面会不断合入新的顶点进来，来扩大连通分量范围。

连通分量可以使用并查集表示。并查集本质就是一个长度为n的数组（n为无向图的顶点数），数组索引值代表图中某个顶点child，数组索引指向的元素值，代表child顶点的祖先顶点father。

初始时，每个child的father都是自己。即初始时，默认有n个连通分量。

本题解法

本题要求的最低成本，其实就是最小生成树所有边相加得到的最小权重和。但是本题中规定了一些“必建高铁的两个城市”，这些“必建高铁的两个城市”是非常有可能形成环的。

我们定义一个minFee来代表最低成本，首先我们需要将必建高铁的成本计算进去。并且在计算的过程中，将必建高铁的两个城市（两个顶点）纳入一个连通分量中（基于并查集）。

之后，我们将“可以建高铁”的列表按照成本费用升序排序（Kruskal算法），然后遍历排序后列表，依次将“可以建高铁”的两个城市（两个顶点）尝试纳入连通分量中，如果有环，则不纳入，无环，则纳入，纳入的话，则将成本费用计入minFee中。

循环结束后，如果并查集中的连通分量数量为1，则说明所有城市（顶点）已经通车，且是最低成本。此时返回minFee就是题解。如果并查集中的连通分量数量不为1，则说明所有城市（顶点）无法连通，返回-1。

二、JavaScript算法源码

这段JavaScript代码用于解决一个特定的问题，即在给定一些城市之间可以修建高铁（以及修建费用）和必须修建高铁的约束条件下，计算满足所有条件的最小高铁修建费用。如果无法满足所有条件，则返回-1。以下是代码的详细讲解：

1. 引入和初始化

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
let n, can, must;

• 引入Node.js的readline模块，用于从控制台读取输入。
• 创建一个readline.Interface实例，以便从标准输入（process.stdin）读取数据，并将输出发送到标准输出（process.stdout）。
• 初始化一个空数组lines来存储输入的每一行。
• 初始化变量n（城市数量）、can（可以修建高铁的线路数量）、must（必须修建的高铁线路数量）。

2. 读取输入

rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 1) {
    [n, can, must] = lines[0].split(" ").map(Number);
  }

  if (
    can !== undefined &&
    must !== undefined &&
    lines.length === can + must + 1
  ) {
    lines.shift();

    const cans = lines
      .splice(0, can)
      .map((line) => line.split(" ").map(Number));

    const musts = lines.map((line) => line.split(" ").map(Number));

    console.log(getResult(n, cans, musts));

    lines.length = 0;
  }
});

• 当从控制台读取到一行输入时，将其添加到lines数组中。
• 如果lines数组只有一行，则这一行包含了n、can、must的值，将其解析并存储。
• 当读取到的行数等于can + must + 1（第一行是n、can、must，接下来can行是可以修建的高铁线路，must行是必须修建的高铁线路），则开始处理这些输入。
• 从lines数组中移除第一行（已经解析为n、can、must），然后分别解析出可以修建的高铁线路（cans）和必须修建的高铁线路（musts）。
• 调用getResult函数计算最小高铁修建费用，并将结果输出到控制台。
• 清空lines数组，以便处理下一组输入。

3. 计算最小高铁修建费用

function getResult(n, cans, musts) {
  // ... (省略中间代码)
}

• getResult函数接收城市数量n、可以修建的高铁线路cans和必须修建的高铁线路musts作为参数。
• 创建一个并查集（UnionFindSet）实例来管理城市的连通性。
• 将cans数组转换为对象cansObj，方便通过城市对（如"1-2"）快速查找修建费用。
• 将musts数组中的元素也转换为城市对的形式。
• 初始化最小费用minFee为0，并遍历musts数组，将必须修建的高铁线路的费用累加到minFee中，并使用并查集将这些线路连接的城市合并到同一个连通分量中。
• 如果所有城市已经通过必须修建的高铁线路连通（即并查集中只有一个连通分量），则直接返回minFee。
• 否则，对cans数组按费用升序排序，然后遍历排序后的cans数组，使用并查集判断是否可以添加当前高铁线路（即判断两个城市是否已经在同一个连通分量中），如果可以，则将其合并，并将费用累加到minFee中。
• 如果遍历完cans数组后，所有城市已经连通（即并查集中只有一个连通分量），则返回minFee；否则，返回-1，表示无法满足所有条件。

4. 并查集实现

class UnionFindSet {
  // ... (省略中间代码)
}

• UnionFindSet类实现了并查集的基本操作，包括初始化、查找根节点（find）和合并两个集合（union）。
• 初始化时，为每个城市创建一个独立的集合，并设置集合的计数count为城市数量n。
• find方法使用路径压缩技术来查找节点的根节点，并将路径上的每个节点直接连接到根节点，以加速后续的查找操作。
• union方法将两个集合合并为一个集合，并更新集合的计数count。

这段代码通过控制台输入读取数据，使用并查集和Kruskal算法求解最小生成树问题，最终计算出满足所有条件的最小高铁修建费用。

三、Java算法源码

import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    // 初始化Scanner对象，用于读取用户输入
    Scanner sc = new Scanner(System.in);

    // 读取城市总数
    int n = sc.nextInt();
    // 读取可以修建高铁的城市对数
    int can = sc.nextInt();
    // 读取必须修建高铁的城市对数
    int must = sc.nextInt();

    // 初始化二维数组cans，用于存储可以修建高铁的城市对及费用
    int[][] cans = new int[can][3];
    for (int i = 0; i < can; i++) {
      cans[i][0] = sc.nextInt(); // 城市1
      cans[i][1] = sc.nextInt(); // 城市2
      cans[i][2] = sc.nextInt(); // 费用
    }

    // 初始化二维数组musts，用于存储必须修建高铁的城市对
    int[][] musts = new int[must][2];
    for (int i = 0; i < must; i++) {
      musts[i][0] = sc.nextInt(); // 城市1
      musts[i][1] = sc.nextInt(); // 城市2
    }

    // 调用getResult方法计算最少费用，并打印结果
    System.out.println(getResult(n, cans, musts));
  }

  /**
   * 计算修建高铁的最少费用
   * 
   * @param n 城市总数
   * @param cans 可以修建高铁的城市对及费用
   * @param musts 必须修建高铁的城市对
   * @return 最少费用，若无法使所有城市通车则返回-1
   */
  public static int getResult(int n, int[][] cans, int[][] musts) {
    // 初始化并查集对象，用于判断城市间的连通性
    UnionFindSet ufs = new UnionFindSet(n);

    // 初始化HashMap cansMap，用于快速查找可以修建高铁的城市对及费用
    HashMap<String, Integer> cansMap = new HashMap<>();
    for (int[] can : cans) {
      int city1 = can[0], city2 = can[1], fee = can[2];
      // 构造城市对的唯一键（保证顺序性，避免重复）
      String key = city1 < city2 ? city1 + "-" + city2 : city2 + "-" + city1;
      cansMap.put(key, fee);
    }

    int minFee = 0; // 初始化最少费用为0

    // 遍历必须修建的高铁，计算费用并合并城市对
    for (int[] must : musts) {
      String key = must[0] < must[1] ? must[0] + "-" + must[1] : must[1] + "-" + must[0];
      minFee += cansMap.get(key); // 将费用加入最少费用中
      ufs.union(must[0], must[1]); // 合并城市对
    }

    // 如果必须修建的高铁已经使所有城市连通，则直接返回最少费用
    if (ufs.count == 1) return minFee;

    // 否则，按照Kruskal算法求解最小生成树
    // 首先，将可以修建的高铁按费用升序排序
    Arrays.sort(cans, (a, b) -> a[2] - b[2]);

    // 遍历排序后的高铁，尝试合并城市对
    for (int[] can : cans) {
      int city1 = can[0], city2 = can[1], fee = can[2];
      // 如果城市对不属于同一个连通分量，则合并它们，并加入费用
      if (ufs.find(city1) != ufs.find(city2)) {
        ufs.union(city1, city2);
        minFee += fee;
      }

      // 如果所有城市已经连通，则提前结束循环
      if (ufs.count == 1) break;
    }

    // 如果循环结束后仍有多个连通分量，则无法使所有城市通车，返回-1
    if (ufs.count > 1) return -1;

    // 返回最少费用
    return minFee;
  }
}

// 并查集类，用于判断城市间的连通性
class UnionFindSet {
  // fa数组用于存储每个城市的父节点，初始时每个城市的父节点都是自己
  int[] fa;
  // count变量用于记录当前的连通分量数
  int count;

  // 构造函数，初始化并查集
  public UnionFindSet(int n) {
    this.fa = new int[n + 1]; // 数组长度为n+1，因为城市编号从1开始
    this.count = n; // 初始时，每个城市都是一个独立的连通分量
    for (int i = 0; i < n + 1; i++) {
      this.fa[i] = i; // 初始化父节点为自己
    }
  }

  // 查找操作，用于找到某个城市的根节点（即连通分量的代表）
  public int find(int x) {
    // 路径压缩优化（但在此讲解中不包含优化，因此保留原始递归查找）
    if (x != this.fa[x]) {
      // 递归查找根节点，并同时更新父节点为根节点（路径压缩优化效果）
      // 但在此处仅保留递归查找，不进行优化
      return (this.fa[x] = this.find(this.fa[x])); // 路径压缩优化语句（此处注释说明）
    }
    return x; // 返回根节点
  }

  // 合并操作，用于合并两个城市对所属的连通分量
  public void union(int x, int y) {
    int x_fa = this.find(x); // 查找x的根节点
    int y_fa = this.find(y); // 查找y的根节点

    // 如果x和y不属于同一个连通分量，则合并它们
    if (x_fa != y_fa) {
      this.fa[y_fa] = x_fa; // 将y的根节点指向x的根节点
      this.count--; // 连通分量数减1
    }
  }
}

在这段代码中，我们首先通过Scanner类读取了用户输入的城市总数、可以修建的高铁信息以及必须修建的高铁信息。然后，我们利用并查集（Union Find Set）数据结构来判断城市间的连通性，并使用Kruskal算法求解最小生成树问题，以计算修建高铁的最少费用。在求解过程中，我们首先处理了必须修建的高铁，并计算了相应的费用。然后，我们按照费用升序排序了可以修建的高铁，并尝试合并城市对，直到所有城市连通或无法再合并为止。最后，我们返回了最少费用或-1（表示无法使所有城市通车）。

四、Python算法源码

这段代码定义了一个 UnionFindSet 类用于处理并查集操作，以及一个 getResult 函数来解决一个特定的问题：给定一系列城市，其中一些城市之间可以修建高铁（以及修建的费用），并且一些城市之间必须修建高铁，求修建所有城市之间高铁的最低成本，或者如果无法使所有城市连通则返回 -1。

# 并差集
class UnionFindSet:
    def __init__(self, n):
        self.fa = [i for i in range(n + 1)]
        self.count = n

    def find(self, x):
        if x != self.fa[x]:
            self.fa[x] = self.find(self.fa[x])
            return self.fa[x]
        return x

    def union(self, x, y):
        x_fa = self.find(x)
        y_fa = self.find(y)

        if x_fa != y_fa:
            self.fa[y_fa] = x_fa
            self.count -= 1


# 算法入口
def getResult(n, cans, musts):
    """
    :param n: 一共几个城市
    :param cans: 哪些城市之间可以修建高铁，以及修建费用
    :param musts: 哪些城市之间必须修建高铁
    :return: 修建城市高铁的最低成本
    """
    ufs = UnionFindSet(n)

    # 这里因为不知道题目用例输入的城市序号是否是按顺序的，因此需要排个序。
    # 并且为了方便统计“必建高铁”的费用，我们需要将cans数组改造为对象，key为'1-2' 两个城市，val为 这两个城市建高铁的费用
    canDict = {}
    for c1, c2, fee in cans:
        key = f"{c1}-{c2}" if c1 < c2 else f"{c2}-{c1}"
        canDict[key] = fee

    # must数组中元素也改造为'1-2' 两个城市字符串的形成，方便从cansObj中获取对应的费用
    musts = map(lambda must: f"{must[0]}-{must[1]}" if must[0] < must[1] else f"{must[1]}-{must[0]}", musts)

    minFee = 0
    for must in musts:
        # 计入必建高铁的费用到minFee中
        minFee += canDict[must]
        c1, c2 = map(int, must.split("-"))
        # 并将必建高铁的两个城市纳入同一个连通分量重
        ufs.union(c1, c2)

    # 如果必建高铁本身已经满足所有城市通车了，那么直接返回minFee
    if ufs.count == 1:
        return minFee

    # 否则，按照求解最小生成树的Kruskal算法，将高铁线（即图的边）按照成本费用（即边的权重）升序
    cans.sort(key=lambda x: x[2])

    # 遍历排序后的cans，每次得到的都是当前的最小权重边
    for c1, c2, fee in cans:
        # 如果对应城市已经接入高铁线（即处于连通分量中）则再次合入就会产生环，因此不能合入，否则就可以合入
        # if ufs.fa[c1] != ufs.fa[c2]:
        if ufs.find(c1) != ufs.find(c2):
            ufs.union(c1, c2)
            # 若可以合入，则将对应的建造成本计入minFee
            minFee += fee

        # 如果此时，所有城市都通车了（即并查集中只有一个连通分量），则提前结束循环
        if ufs.count == 1:
            break

    # 如果循环完，发现并查集中还有多个连通分量，那么代表有的城市无法通车，因此返回-1
    if ufs.count > 1:
        return -1

    return minFee


# 输入获取
n, can, must = map(int, input().split())
cans = [list(map(int, input().split())) for i in range(can)]
musts = [list(map(int, input().split())) for i in range(must)]

# 算法调用
print(getResult(n, cans, musts))

这里是代码的主要逻辑解释：

1. 并查集类 (UnionFindSet):

   • 初始化时，每个城市（或节点）都是一个独立的连通分量，fa 数组用于存储每个节点的父节点（代表元素）。
   • find 方法用于查找某个节点的根（代表元素），同时进行了路径压缩以优化后续查找操作。
   • union 方法用于合并两个连通分量，同时更新连通分量的数量。

2. getResult 函数:

   • 输入参数包括城市总数 n，可以修建的高铁列表 cans（每个元素包含两个城市编号和修建费用），以及必须修建的高铁列表 musts（每个元素包含两个城市编号）。
   • 首先，将可以修建的高铁列表 cans 转换为一个字典 canDict，以便通过城市对（按升序排列的城市编号组成的字符串）快速查找修建费用。
   • 然后，遍历必须修建的高铁列表 musts，将对应的费用加到 minFee 中，并通过并查集将相应的城市对合并。
   • 如果在合并必须修建的高铁后，所有城市已经连通（即并查集中只有一个连通分量），则直接返回 minFee。
   • 否则，对可以修建的高铁列表 cans 按费用进行排序，然后遍历排序后的列表，使用并查集判断是否可以在不形成环的情况下合并城市对，如果可以，则将对应的费用加到 minFee 中。
   • 如果遍历完所有可以修建的高铁后，仍然无法使所有城市连通（即并查集中有多个连通分量），则返回 -1。

3. 输入与输出:

   • 从标准输入读取城市总数 n，可以修建的高铁数量 can，以及必须修建的高铁数量 must。
   • 接着读取 can 行，每行包含三个整数，表示两个城市编号和修建费用。
   • 然后读取 must 行，每行包含两个整数，表示必须修建高铁的两个城市编号。
   • 最后，调用 getResult 函数并打印结果。

这个算法结合了并查集和 Kruskal 算法的思想，以有效地解决最小生成树问题，同时考虑了必须包含的边（即必须修建的高铁）。

五、C/C++算法源码：

C++ 代码实现

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

// 并查集类
class UnionFindSet {
public:
    vector<int> fa; // 存储每个节点的父节点
    int count;      // 连通分量的数量

    // 构造函数，初始化并查集
    UnionFindSet(int n) {
        fa.resize(n + 1);
        for (int i = 1; i <= n; i++) {
            fa[i] = i; // 初始时，每个节点的父节点是自己
        }
        count = n; // 初始时，连通分量的数量为n
    }

    // 查找操作，带路径压缩
    int find(int x) {
        if (x != fa[x]) {
            fa[x] = find(fa[x]); // 路径压缩
        }
        return fa[x];
    }

    // 合并操作
    void unionSet(int x, int y) {
        int x_fa = find(x);
        int y_fa = find(y);

        if (x_fa != y_fa) {
            fa[y_fa] = x_fa; // 将y的父节点指向x的父节点
            count--;         // 连通分量数量减1
        }
    }
};

// 算法入口
int getResult(int n, vector<vector<int>>& cans, vector<vector<int>>& musts) {
    UnionFindSet ufs(n);

    // 将cans数组改造为map，key为"c1-c2"，value为费用
    map<string, int> canDict;
    for (auto& can : cans) {
        int c1 = can[0], c2 = can[1], fee = can[2];
        string key = (c1 < c2) ? to_string(c1) + "-" + to_string(c2) : to_string(c2) + "-" + to_string(c1);
        canDict[key] = fee;
    }

    // 将musts数组改造为"c1-c2"的形式
    vector<string> mustKeys;
    for (auto& must : musts) {
        int c1 = must[0], c2 = must[1];
        string key = (c1 < c2) ? to_string(c1) + "-" + to_string(c2) : to_string(c2) + "-" + to_string(c1);
        mustKeys.push_back(key);
    }

    int minFee = 0;
    for (auto& must : mustKeys) {
        // 计入必建高铁的费用
        minFee += canDict[must];
        int c1 = stoi(must.substr(0, must.find('-')));
        int c2 = stoi(must.substr(must.find('-') + 1));
        // 将必建高铁的两个城市纳入同一个连通分量
        ufs.unionSet(c1, c2);
    }

    // 如果必建高铁已经满足所有城市通车，直接返回minFee
    if (ufs.count == 1) {
        return minFee;
    }

    // 按照费用升序排序
    sort(cans.begin(), cans.end(), [](vector<int>& a, vector<int>& b) {
        return a[2] < b[2];
    });

    // 遍历排序后的cans
    for (auto& can : cans) {
        int c1 = can[0], c2 = can[1], fee = can[2];
        // 如果两个城市不在同一个连通分量中，则可以合并
        if (ufs.find(c1) != ufs.find(c2)) {
            ufs.unionSet(c1, c2);
            minFee += fee;
        }

        // 如果所有城市都通车了，提前结束循环
        if (ufs.count == 1) {
            break;
        }
    }

    // 如果还有多个连通分量，返回-1
    if (ufs.count > 1) {
        return -1;
    }

    return minFee;
}

int main() {
    int n, can, must;
    cin >> n >> can >> must;

    vector<vector<int>> cans(can, vector<int>(3));
    for (int i = 0; i < can; i++) {
        cin >> cans[i][0] >> cans[i][1] >> cans[i][2];
    }

    vector<vector<int>> musts(must, vector<int>(2));
    for (int i = 0; i < must; i++) {
        cin >> musts[i][0] >> musts[i][1];
    }

    cout << getResult(n, cans, musts) << endl;

    return 0;
}

---

C 语言代码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 1000

// 并查集结构体
typedef struct {
    int fa[MAX_N + 1]; // 存储每个节点的父节点
    int count;         // 连通分量的数量
} UnionFindSet;

// 初始化并查集
void initUnionFindSet(UnionFindSet* ufs, int n) {
    for (int i = 1; i <= n; i++) {
        ufs->fa[i] = i; // 初始时，每个节点的父节点是自己
    }
    ufs->count = n; // 初始时，连通分量的数量为n
}

// 查找操作，带路径压缩
int find(UnionFindSet* ufs, int x) {
    if (x != ufs->fa[x]) {
        ufs->fa[x] = find(ufs, ufs->fa[x]); // 路径压缩
    }
    return ufs->fa[x];
}

// 合并操作
void unionSet(UnionFindSet* ufs, int x, int y) {
    int x_fa = find(ufs, x);
    int y_fa = find(ufs, y);

    if (x_fa != y_fa) {
        ufs->fa[y_fa] = x_fa; // 将y的父节点指向x的父节点
        ufs->count--;         // 连通分量数量减1
    }
}

// 算法入口
int getResult(int n, int cans[][3], int canCount, int musts[][2], int mustCount) {
    UnionFindSet ufs;
    initUnionFindSet(&ufs, n);

    // 将cans数组改造为map，key为"c1-c2"，value为费用
    char key[20];
    int canDict[MAX_N * MAX_N];
    memset(canDict, -1, sizeof(canDict)); // 初始化为-1

    for (int i = 0; i < canCount; i++) {
        int c1 = cans[i][0], c2 = cans[i][1], fee = cans[i][2];
        sprintf(key, "%d-%d", c1 < c2 ? c1 : c2, c1 < c2 ? c2 : c1);
        canDict[atoi(key)] = fee;
    }

    // 将musts数组改造为"c1-c2"的形式
    int minFee = 0;
    for (int i = 0; i < mustCount; i++) {
        int c1 = musts[i][0], c2 = musts[i][1];
        sprintf(key, "%d-%d", c1 < c2 ? c1 : c2, c1 < c2 ? c2 : c1);
        minFee += canDict[atoi(key)];
        unionSet(&ufs, c1, c2);
    }

    // 如果必建高铁已经满足所有城市通车，直接返回minFee
    if (ufs.count == 1) {
        return minFee;
    }

    // 按照费用升序排序
    for (int i = 0; i < canCount - 1; i++) {
        for (int j = i + 1; j < canCount; j++) {
            if (cans[i][2] > cans[j][2]) {
                int temp[3];
                memcpy(temp, cans[i], sizeof(temp));
                memcpy(cans[i], cans[j], sizeof(temp));
                memcpy(cans[j], temp, sizeof(temp));
            }
        }
    }

    // 遍历排序后的cans
    for (int i = 0; i < canCount; i++) {
        int c1 = cans[i][0], c2 = cans[i][1], fee = cans[i][2];
        if (find(&ufs, c1) != find(&ufs, c2)) {
            unionSet(&ufs, c1, c2);
            minFee += fee;
        }

        // 如果所有城市都通车了，提前结束循环
        if (ufs.count == 1) {
            break;
        }
    }

    // 如果还有多个连通分量，返回-1
    if (ufs.count > 1) {
        return -1;
    }

    return minFee;
}

int main() {
    int n, can, must;
    scanf("%d %d %d", &n, &can, &must);

    int cans[can][3];
    for (int i = 0; i < can; i++) {
        scanf("%d %d %d", &cans[i][0], &cans[i][1], &cans[i][2]);
    }

    int musts[must][2];
    for (int i = 0; i < must; i++) {
        scanf("%d %d", &musts[i][0], &musts[i][1]);
    }

    printf("%d
", getResult(n, cans, can, musts, must));

    return 0;
}

---

代码讲解

1. 并查集（Union-Find Set）

• 功能：用于管理元素的连通性，支持查找和合并操作。
• 路径压缩：在查找时，将路径上的所有节点直接指向根节点，减少后续查找的时间复杂度。
• 合并操作：将两个集合合并为一个集合，同时减少连通分量的数量。

2. 算法流程

1. 初始化并查集：每个城市初始时都是一个独立的连通分量。
2. 处理必建高铁：
   • 将必建高铁的费用计入总成本。
   • 将必建高铁的两个城市合并到同一个连通分量中。
3. 处理可选高铁：
   • 按照费用升序排序。
   • 遍历每条可选高铁，如果两个城市不在同一个连通分量中，则合并并计入费用。
4. 检查连通性：如果所有城市都在同一个连通分量中，返回总成本；否则返回-1。

3. 复杂度分析

• 时间复杂度：主要取决于排序和并查集操作，总体为 (O(M log M))，其中 (M) 是高铁线路的数量。
• 空间复杂度：主要用于存储并查集和高铁线路信息，为 (O(N + M))。

通过以上代码和讲解，您可以清晰地理解并查集的应用以及如何解决最小生成树问题。

六、尾言

什么是华为OD？

华为OD（Outsourcing Developer，外包开发工程师）是华为针对软件开发工程师岗位的一种招聘形式，主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分，算法题的机试至关重要。

为什么刷题很重要？

1. 机试是进入技术面的第一关：
   华为OD机试（常被称为机考）主要考察算法和编程能力。只有通过机试，才能进入后续的技术面试环节。

2. 技术面试需要手撕代码：
   技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。

3. 入职后的可信考试：
   入职华为后，还需要通过“可信考试”。可信考试分为三个等级：

   • 入门级：主要考察基础算法与编程能力。
   • 工作级：更贴近实际业务需求，可能涉及复杂的算法或与工作内容相关的场景题目。
   • 专业级：最高等级，考察深层次的算法以及优化能力，与薪资直接挂钩。

刷题策略与说明：

2024年8月14日之后，华为OD机试的题库转为 E卷，由往年题库（D卷、A卷、B卷、C卷）和全新题目组成。刷题时可以参考以下策略：

1. 关注历年真题：

   • 题库中的旧题占比较大，建议优先刷历年的A卷、B卷、C卷、D卷题目。
   • 对于每道题目，建议深度理解其解题思路、代码实现，以及相关算法的适用场景。

2. 适应新题目：

   • E卷中包含全新题目，需要掌握全面的算法知识和一定的灵活应对能力。
   • 建议关注新的刷题平台或交流群，获取最新题目的解析和动态。

3. 掌握常见算法：
   华为OD考试通常涉及以下算法和数据结构：

   • 排序算法（快速排序、归并排序等）
   • 动态规划（背包问题、最长公共子序列等）
   • 贪心算法
   • 栈、队列、链表的操作
   • 图论（最短路径、最小生成树等）
   • 滑动窗口、双指针算法

4. 保持编程规范：

   • 注重代码的可读性和注释的清晰度。
   • 熟练使用常见编程语言，如C++、Java、Python等。

如何获取资源？

1. 官方参考：

   • 华为招聘官网或相关的招聘平台会有一些参考信息。
   • 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。

2. 加入刷题社区：

   • 找到可信的刷题交流群，与其他备考的小伙伴交流经验。
   • 关注知名的刷题网站，如LeetCode、牛客网等，这些平台上有许多华为OD的历年真题和解析。

3. 寻找系统性的教程：

   • 学习一本经典的算法书籍，例如《算法导论》《剑指Offer》《编程之美》等。
   • 完成系统的学习课程，例如数据结构与算法的在线课程。

积极心态与持续努力：

刷题的过程可能会比较枯燥，但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试，还是为了未来的职业发展，这些积累都会成为重要的财富。

考试注意细节

1. 本地编写代码

   • 在本地 IDE（如 VS Code、PyCharm 等）上编写、保存和调试代码，确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误，提高代码准确性。

2. 调整心态，保持冷静

   • 遇到提示不足或实现不确定的问题时，不必慌张，可以采用更简单或更有把握的方法替代，确保思路清晰。

3. 输入输出完整性

   • 注意训练和考试时都需要编写完整的输入输出代码，尤其是和题目示例保持一致。完成代码后务必及时调试，确保功能符合要求。

4. 快捷键使用

   • 删除行可用 Ctrl+D，复制、粘贴和撤销分别为 Ctrl+C，Ctrl+V，Ctrl+Z，这些可以正常使用。
   • 避免使用 Ctrl+S，以免触发浏览器的保存功能。

5. 浏览器要求

   • 使用最新版的 Google Chrome 浏览器完成考试，确保摄像头开启并正常工作。考试期间不要切换到其他网站，以免影响考试成绩。

6. 交卷相关

   • 答题前，务必仔细查看题目示例，避免遗漏要求。
   • 每完成一道题后，点击【保存并调试】按钮，多次保存和调试是允许的，系统会记录得分最高的一次结果。完成所有题目后，点击【提交本题型】按钮。
   • 确保在考试结束前提交试卷，避免因未保存或调试失误而丢分。

7. 时间和分数安排

   • 总时间：150 分钟；总分：400 分。
   • 试卷结构：2 道一星难度题（每题 100 分），1 道二星难度题（200 分）。及格分为 150 分。合理分配时间，优先完成自己擅长的题目。

8. 考试环境准备

   • 考试前请备好草稿纸和笔。考试中尽量避免离开座位，确保监控画面正常。
   • 如需上厕所，请提前规划好时间以减少中途离开监控的可能性。

9. 技术问题处理

   • 如果考试中遇到断电、断网、死机等技术问题，可以关闭浏览器并重新打开试卷链接继续作答。
   • 出现其他问题，请第一时间联系 HR 或监考人员进行反馈。

祝你考试顺利，取得理想成绩！