第十四届蓝桥杯 Java B 组国赛 G 题—— 电动车（AC）

1. 电动车

前置知识点：最小生成树

1. 问题描述

作为一位繁忙的程序员，小蓝经常需要在 $N$ 座城市之间来回穿梭。他准备购买一辆电动车出行，但是担心电动车电量不足。

为了描述方便，我们把 $N$ 座城市编号 $1$ 至 $N$。城市之间一共有 $M$ 条双向高速公路相连。其中第 $i$ 条连接 $u_i$ 号城市和 $v_i$ 号城市，耗费 $w_i$ 个单位的电量。

假设小蓝可以在出发城市，以及任何中途经过的城市充满电。小蓝想知道，如果希望从任意城市开电动车到任意另一个城市，都可以找到一条由若干高速公路组成路径，使得不需要在任何高速公路内补充电量，那么这台电动车至少需要多少电量？

2. 输入描述

第一行包含两个整数 $N$ 和 $M$。

以下 $M$ 行，每行包含 $3$ 个整数 $u_i$、$v_i$ 和 $w_i$。

3. 输出描述

一个整数，代表答案。

如果存在两个城市不能通过高速公路相互到达，输出 $-1$。

4. 样例输入

4 5
1 2 3
1 3 5
2 4 2
4 3 2
4 1 4

5. 样例输出

3

6. 样例说明

从 $1$ 到 $2$ 可以走：$1\to 2$，需要电量 $3$。

从 $1$ 到 $3$ 可以走：$1\to 2\to 4\to 3$，其中 $1\to 2$ 需要电量 $3$，$2\to 4$ 需要电量 $2$，$4\to 3$ 需要电量 $2$，全程至少需要电量 $3$。

从 $1$ 到 $4$ 可以走：$1\to 2\to 4$，其中 $1\to 2$ 需要电量 $3$，$2\to 4$ 需要电量 $2$，全程至少需要电量 $3$。

从 $2$ 到 $3$ 可以走：$2\to 4\to 3$，其中 $2\to 4$ 需要电量 $2$，$4\to 3$ 需要电量 $2$，全程至少需要电量 $2$。

从 $2$ 到 $4$ 可以走：$2\to 4$，需要电量 $2$。

从 $3$ 到 $4$ 可以走：$3\to 4$，需要电量 $2$。

综上所述，电动车至少需要 $3$ 个单位的电量。

7. 评测用例规模

对于 $20\%$ 的数据，$1\le N,M\le 100$，$0\le w_i\le 100$。

对于 $100\%$ 的数据，$1\le N,M\le 200000$，$0\le w_i\le 10^9$。

8. 原题链接

电动车

2. 解题思路

在这道题目里，我们并非计算一条路径上所有边的权值之和，而是要找出路径上所有边权值的最大值。我们定义 $f(u,v)$ 为从点 $u$ 到点 $v$ 的最短路，而题目所要求的则是：
$$\underset{1\le u,v\le n}{\max }f(u,v)$$
通常这类问题都与 Kruskal 算法（一种求解最小生成树的算法）紧密相关。如果你对 Kruskal 的理解还不够深入，可以参考这个链接：https://oi-wiki.org/graph/mst/。

让我们简单回顾一下 Kruskal 算法的执行步骤：

1. 将所有边按照权值从小到大进行排序。
2. 初始化一个并查集，最初每个点都独立地属于一个集合。
3. 按边权从小到大遍历所有边，如果一条边所连接的两个节点不在同一个集合中，那么就将它们所在的两个集合合并。

在观察步骤三时，我们可以发现一个现象：当遍历到某条权值为 $g$ 的边，并且我们合并了这条边连接的两个节点所在的集合 $a,b$。那么，对于集合 $a$ 中的任意节点 $u$ 和集合 $b$ 中的任意节点 $v$，我们都有 $f(u,v)=g$。

为什么会这样呢？

原因在于：我们是按照边权从小到大进行遍历的，所以当我们进行了集合合并操作时，意味着从集合 $a$ 中的任意节点到集合 $b$ 中的任意节点所经过的最大边权一定是当前合并的这条边。

基于上述分析，我们可以知道：我们所需要找的任意两点间最短路的最大值，就是在 Kruskal 算法中最后一次进行集合合并操作时的边权。对于含有 $n$ 个节点的最小生成树，总共会有 $n-1$ 条边，也就是说会进行 $n-1$ 次集合合并操作。我们称那些在遍历过程中会导致集合合并的边为有效边，那么第 $n-1$ 大的有效边的权值就是我们所要求的答案。

如果最后这个图无法被完全连接，即有效边的数量不满 $n-1$ 条，那么就输出 $-1$，表示无解。

时间复杂度：$O(m\log m)$。

3. AC_Code

• C++

#include <bits/stdc++.h>
using namespace std;

int n, m;
struct UF
{
    
    std::vector<int> f, siz;
    UF(int n) : f(n), siz(n, 1) {
     std::iota(f.begin(), f.end(), 0); }
    int find(int x)
    {
    
        while (x != f[x])
            x = f[x] = f[f[x]];
        return x;
    }
    bool same(int x, int y) {
     return find(x) == find(y); }
    bool merge(int x, int y)
    {
    
        x = find(x);
        y = find(y);
        if (x == y)
            return false;
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    int size(int x) {
     return siz[find(x)]; }
};
int main()
{
    
    cin >> n >> m;
    UF uf(n);
    vector<array<int, 3>> a(m);
    for (int i = 0; i < m; ++i)
    {
    
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        a[i] = {
    w, u, v};
    }
    sort(a.begin(), a.end());
    int x = 0;
    for (int i = 0; i < m; ++i)
    {
    
        int w = a[i][0], u = a[i][1], v = a[i][2];
        if (!uf.same(u, v))
        {
    
            x++;
            if (x == n - 1)
            {
    
                cout << w << '\n';
                return 0;
            }
            uf.merge(u, v);
        }
    }
    cout << -1 << '\n';
    return 0;
}

• Java

import java.util.*;

public class Main {
    
    static int n, m;
    static int[] parent, size;
    
    public static void main(String[] args) {
    
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        parent = new int[n];
        size = new int[n];
        for (int i = 0; i < n; ++i) {
    
            parent[i] = i;
            size[i] = 1;
        }
        
        int[][] edges = new int[m][3];
        for (int i = 0; i < m; ++i) {
    
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            int w = sc.nextInt();
            edges[i] = new int[]{
    w, u, v};
        }
        Arrays.sort(edges, Comparator.comparingInt(a -> a[0]));
        
        int x = 0;
        for (int i = 0; i < m; ++i) {
    
            int w = edges[i][0], u = edges[i][1], v = edges[i][2];
            if (!same(u, v)) {
    
                x++;
                if (x == n - 1) {
    
                    System.out.println(w);
                    return;
                }
                merge(u, v);
            }
        }
        System.out.println(-1);
    }

    static int find(int x) {
    
        if (parent[x] != x) {
    
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    static boolean (int x, int y) {
    
        return find(x) == find(y);
    }

    static void merge(int x, int y) {
    
        x = find(x);
        y = find(y);
        if (x != y) {
    
            if (size[x] < size[y]) {
    
                int temp = x;
                x = y;
                y = temp;
            }
            parent[y] = x;
            size[x] += size[y];
        }
    }
}

• Python

n, m = map(int, input().split())
parent = list(range(n))
size = [1] * n

edges = []
for _ in range(m):
    u, v, w = map(int, input().split())
    u -= 1
    v -= 1
    edges.append((w, u, v))
edges.sort()

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def same(x, y):
    return find(x) == find(y)

def merge(x, y):
    x, y = find(x), find(y)
    if x != y:
        if size[x] < size[y]:
            x, y = y, x
        parent[y] = x
        size[x] += size[y]

x = 0
for w, u, v in edges:
    if not same(u, v):
        x += 1
        if x == n - 1:
            print(w)
            break
        merge(u, v)
else:
    print(-1)