首页 > 试题广场 >

寻宝

[编程题]寻宝

热度指数：3305 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

亮亮解出了卷轴隐藏的秘密，来到了一片沼泽地。这里有很多空地，而面试直通卡可能埋在任意一块空地中，好在亮亮发现了一堆木材，他可以将木材铺在两个空地之间的沼泽地上。因为亮亮不知道面试直通卡具体在哪一块空地中，所以必须要保证任意一块空地对于亮亮来说是可以抵达的。 “怎么还有鳄鱼！没办法，看来有些空地不能直接到达了。” 亮亮虽然没有洁癖，但是沼泽地实在太臭了，所以亮亮不会循环利用木材。而且木材不能拼接在一起使用，所以亮亮必须要知道在耗费木材最少的情况下，最长的那根木材至少需要多长。

输入描述:

第一行包含两个整数N(1≤N≤10000),M(1≤M≤1000000)。N表示公有N块空地。
接下来M行，每行包含三个整数P(1≤P≤N),Q(1≤Q≤N),K代表P,Q两个间没有鳄鱼，需要耗费K的木材。

输出描述:

一个整数，即耗费木材最少的情况下，最长的那根木材长度。

示例1

输入

输出

算法知识视频讲解

Java

Sen🍓🍀

import java.util.*;

// 最小生成树：Kruskal
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        int[][] edge = new int[m][3];
        for (int i = 0; i < m; i++) {
            int p = in.nextInt() - 1, q = in.nextInt() - 1, k = in.nextInt();
            edge[i][0] = p;
            edge[i][1] = q;
            edge[i][2] = k;
        }

        Arrays.sort(edge, (e1, e2)->e1[2] - e2[2]); // 边长 升序

        int max = 0;
        UnionFind uf = new UnionFind(n);
        for (int[] e : edge) {
            int p = e[0], q = e[1], k = e[2];
            if (uf.union(p, q)) {
                max = Math.max(max, k);
            }
        }
        System.out.println(max);
    }
}
// 并查集
class UnionFind {
    int[] parent;
    int[] rank;
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

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

    public boolean union(int x, int y) {
        int rootX = find(x), rootY = find(y);
        if (rootX == rootY) return false;

        if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        return true;
    }
}

发表于 2025-07-02 08:18:28 回复(0)

Java

Felix404

使用Kruskal最小生成树算法，双100%

import java.util.*;

class Edge implements Comparable{
    int node1;
    int node2;
    int value;
    public Edge(int node1, int node2, int value){
        this.node1 = node1;
        this.node2 = node2;
        this.value = value;
    }
    public int compareTo(Object o){
        Edge edge = (Edge)o;
        if(this.value > edge.value)
            return 1;
        else if(this.value < edge.value)
            return -1;
        else
            return 0;
    }
}

class Solution{
    int n;
    int m;
    int[] parent;
    Edge[] edges;
    
    // 并查集找到父节点
    public int find(int x){
        if(parent[x] != x){
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    public void run(){
        Scanner reader = new Scanner(System.in);
        while(reader.hasNext()){
            n = reader.nextInt();
            m = reader.nextInt();
            if(n == 1)
                System.out.println(0);
            // 并查集初始化 父节点
            parent = new int[n + 1];
            for(int i = 1; i <= n; i++){
                parent[i] = i;
            }
            // 初始化所有edge
            edges = new Edge[m];
            for(int i = 0; i < m; i++){
                edges[i] = new Edge(reader.nextInt(), reader.nextInt(), reader.nextInt());
            }
            Arrays.sort(edges);

            // 一条边一条边判断
            int cntNode = 0;
            for(int i = 0; i < m; i++){
                Edge cur = edges[i];
                int node1 = cur.node1;
                int node2 = cur.node2;
                int node1Parent = find(node1);
                int node2Parent = find(node2);
                // 每次选择不属于同一棵树的edge
                if(parent[node1] != parent[node2]){
                    parent[node1Parent] = node2Parent;
                    cntNode++;
                }
                if(cntNode == n-1){
                    System.out.println(cur.value);
                    return;
                }
            }
        }
    }
}

public class Main{
    public static void main(String[] args){
        Solution solution = new Solution();
        solution.run();
    }
}

发表于 2021-03-15 15:17:51 回复(0)