2022.03.19京东算法第二题建造规划

题目描述：

小明在玩一款建造类的游戏。他需要为一段未开荒的地段设计路段的规划，以便起重机通过。

游戏里每段路径都有能承重的级别，小明现在希望尽可能让能承受更大的起重机通过，这样他就可以比较快地完成建造了。

游戏规定小明只能选一种起重机机型，小明想知道这个起重机最高的承重级别应该是多少，使得在该承重条件下，起重机可以从任何一个点出发去向任何一个点而不会损坏道路（损坏道路指的是路段上行驶了超过承重能力的起重机）。

为了方便，我们将需要规划的建造点抽象成N个点，有M条边将他们相连。

输入描述：

第一行是两个空格隔开的正整数n, m。n代表点数，我们将点从1到n编号，m指边的数量

接下来m行，每行3个空格隔开的正整数u, v, p，代表节点u和节点v之间有一条承重能力为p的路径

1≤n≤1000, 1≤m≤min{n*(n + 1)/2,10000}

输出描述：

一行，一个正整数，表示起重机的最重承重级别

输入样例：

3 3
1 2 3
1 3 4
2 3 5

样例输出：

4

提示：

样例解释

重量为5时，从点1到点3无法完成（超出了最大承重），而重量为4时可以任意两点间到达。因此最重可以是4.

import java.util.HashSet;
import java.util.Scanner;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[][] path = new int[m][3];
        int weight = 0;
        for(int i = 0;i < m;i++){
            for(int j = 0;j < 3;j++){
                path[i][j] = sc.nextInt();
                if(j == 2){
                    // 找出最大的weight值4
                    weight = Math.max(weight, path[i][j]);
                }
            }
        }
        HashSet set = new HashSet<>();
        // 最大的weight值递减，直到找到满足条件的
        
        while (weight >= 0){
            int edge = 0;
            for(int i = 0;i < m;i++){
                if(path[i][2] >= weight){
                    set.add(path[i][0]);
                    set.add(path[i][1]);
                    edge++;
                }
            }
            // 当满足条件的时候是edge >= n - 1并且set.size() == n
            if(edge >= n - 1 && set.size() == n){
                break;
            }
            weight--;
        }
        System.out.println(weight);
    }
}