蓝桥杯（聪明的猴子）克鲁斯卡尔算法最小生成树

题目描述
在一个热带雨林中生存着一群猴子，它们以树上的果子为生。昨天下了一场大雨，现在雨过天晴，但整个雨林的地表还是被大水淹没着，部分植物的树冠露在水面上。猴子不会游泳，但跳跃能力比较强，它们仍然可以在露出水面的不同树冠上来回穿梭，以找到喜欢吃的果实。

现在，在这个地区露出水面的有 N 棵树，假设每棵树本身的直径都很小，可以忽略不计。我们在这块区域上建立直角坐标系，则每一棵树的位置由其所对应的坐标表示(任意两棵树的坐标都不相同)。

在这个地区住着的猴子有 M 个，下雨时，它们都躲到了茂密高大的树冠中，没有被大水冲走。由于各个猴子的年龄不同、身体素质不同，它们跳跃的能力不同。有的猴子跳跃的距离比较远(当然也可以跳到较近的树上)，而有些猴子跳跃的距离就比较近。这些猴子非常聪明，它们通过目测就可以准确地判断出自己能否跳到对面的树上。

现已知猴子的数量及每一个猴子的最大跳跃距离，还知道露出水面的每一棵树的坐标，你的任务是统计有多少个猴子可以在这个地区露出水面的所有树冠上觅食。

输入描述
第 1 行为一个整数，表示猴子的个数 (2≤M≤500)；

第 2 行为 M 个整数，依次表示猴子的最大跳跃距离（每个整数值在 1∼1000之间）；

第 3 行为一个整数表示树的总棵数 (2≤N≤1000)；

第 4 行至第 N+3 行为 N 棵树的坐标（横纵坐标均为整数，范围为：−1000∼1000）。

（同一行的整数间用空格分开）

输出描述
输出一个整数，表示可以在这个地区的所有树冠上觅食的猴子数。

输入输出样例
示例 1

输入

4
1 2 3 4
6
0 0
1 0
1 2
-1 -1
-2 0
2 2

输出

3

运行限制
语言 最大运行时间 最大运行内存
C++ 1s 256M
C 1s 256M
Java 2s 256M
Python3 3s 256M
题目思路:

    首先读完题目就知道他要求的是最小生成树,通过最小生成树可以得到各个联通点之间的距离，找到最大距离我们就可以和那些猴子的跳远距离比较，如果比他小则可以通过



    我们还需要知道每两个点之间的距离，可以用公式sqrt((x1-x2)^2+(y1-y2)^2) 求出距离，把这些所求的距离放入一个类中保存，后期比较还需要用

    最后我们生成最小生成树来比较就可以了

看看代码:

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class 聪明的猴子 {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    Scanner sc = new Scanner(System.in);
    int m = sc.nextInt();// 猴子的个数
    int[] a = new int[m];// 每只猴子的跳跃距离
    for (int i = 0; i < m; i++) {
        a[i] = sc.nextInt();
    }
    int n = sc.nextInt();// 树的个数
    Tree[] p = new Tree[n];
    Treedata[] q = new Treedata[((n - 1) * n / 2)];
    Treedata[] mintree = new Treedata[n - 1];
    int k = 0;
    int t = n;
    while (t > 0) {
        int x = sc.nextInt();
        int y = sc.nextInt();
        p[k] = new Tree(k, x, y);
        k++;
        t--;
    }
    k = 0;
    for (int i = 0; i < p.length; i++) {
        for (int j = i + 1; j < p.length; j++) {
            q[k] = new Treedata(p[i].id, p[j].id,
                    Math.sqrt(Math.pow(p[j].x - p[i].x, 2) + Math.pow(p[j].y - p[i].y, 2)));
            k++;
        }
    }

// for (int i = 0; i < k; i++) {
// System.out.println(q[i].x + " " + q[i].y + " " + q[i].dis);
// }

    int[] d = new int[n];

    for (int i = 0; i < n; i++) {
        d[i] = i;
    }

    Arrays.sort(q, new Comparator<Treedata>() {

        @Override
        public int compare(Treedata o1, Treedata o2) {
            // TODO Auto-generated method stub
            return new Double(o1.dis).compareTo(new Double(o2.dis));
        }
    });

// for (int i = 0; i < k; i++) {
// System.out.println(q[i].x + " " + q[i].y + " " + q[i].dis);
// }

    int num = 0;
    for (int i = 0; i < k; i++) {
        int initial = q[i].x;
        int end = q[i].y;
        if (d[initial] != d[end]) {
            mintree[num] = q[i];
            num++;
            int elem = d[end];
            for (int j = 0; j < n; j++) {
                if (d[j] == elem) {
                    d[j] = d[initial];
                }
            }
        }
        if (num == n - 1) {
            break;
        }
    }

// for (int i = 0; i < n - 1; i++) {
// System.out.println(mintree[i].x + " " + mintree[i].y + " " + mintree[i].dis);
// }

    double max = 0;
    for (int i = 0; i < n - 1; i++) {
        max = Math.max(mintree[i].dis, max);
    }

// System.out.println((int) Math.ceil(max));

    int count = 0;
    for (int i = 0; i < m; i++) {
        if (a[i] >= (int) Math.ceil(max)) {
            count++;
        }
    }
    System.out.println(count);
}

}

//树类
class Tree {

public int id;
public int x;
public int y;

public Tree(int id, int x, int y) {
    this.id = id;
    this.x = x;
    this.y = y;
}

}

class Treedata implements Comparable {

public int x;
public int y;
public double dis;

public Treedata(int x, int y, double dis) {
    this.x = x;
    this.y = y;
    this.dis = dis;
}

@Override
public int compareTo(Treedata o) {
    // TODO Auto-generated method stub
    return 0;
}

}