首页 > 试题广场 >

寻宝

[编程题]寻宝

热度指数：3186 时间限制：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

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)