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

叁歲伎倆 2024-04-20 11:58 91阅读 0赞

#### 目录 ####

*  1. 电动车
 *   *  1. 问题描述
     *  2. 输入描述
     *  3. 输出描述
     *  4. 样例输入
     *  5. 样例输出
     *  6. 样例说明
     *  7. 评测用例规模
     *  8. 原题链接
 *  2. 解题思路
 *  3. AC\_Code

## 1. 电动车 ##

前置知识点：最小生成树

### 1. 问题描述 ###

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

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

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

### 2. 输入描述 ###

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

以下  M M M 行，每行包含  3 3 3 个整数  u i u\_i ui、 v i v\_i vi 和  w i w\_i wi。

### 3. 输出描述 ###

一个整数，代表答案。

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

### 4. 样例输入 ###

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

### 5. 样例输出 ###

### 6. 样例说明 ###

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

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

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

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

从  2 2 2 到  4 4 4 可以走： 2 → 4 2 \\rightarrow 4 2→4，需要电量  2 2 2。

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

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

### 7. 评测用例规模 ###

对于  20 % 20\\% 20% 的数据， 1 ≤ N , M ≤ 100 1 \\le N, M \\le 100 1≤N,M≤100， 0 ≤ w i ≤ 100 0 \\le w\_i \\le 100 0≤wi≤100。

对于  100 % 100\\% 100% 的数据， 1 ≤ N , M ≤ 200000 1 \\le N, M \\le 200000 1≤N,M≤200000， 0 ≤ w i ≤ 1 0 9 0 \\le w\_i \\le 10^9 0≤wi≤109。

### 8. 原题链接 ###

[电动车][Link 1]

## 2. 解题思路 ##

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

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

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

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

为什么会这样呢？

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

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

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

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

## 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)

[Link 1]: https://www.lanqiao.cn/problems/6250/learning/