题目链接:P1991 无线通讯网

这是一道最小生成树的题目.在计算出最小生成树后,将使用卫星电话的最大值去除即可.

小优化:

在并查集中,为了find的节点层级尽可能少,在union的时候将低层级的树并入高层级,这样能够减少树的高度.

所以代码里使用level记录find时候的高度,在union的时候,根据这个判断来进行union.

以下是代码:

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
static int[] pointIdx;
static Point[] points;
static BufferedReader br;
static StringTokenizer st;
static PriorityQueue pq;
static PriorityQueue ans;
static boolean[][] hasAdd;
static int[] level;
public static void main(String[] args) throws Exception {
br = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(br.readLine());
int S = Integer.parseInt(st.nextToken());
int P = Integer.parseInt(st.nextToken());
init(P);
points = new Point[P+1];
int px;
int py;
for(int i = 1;i<=P;i++){
st = new StringTokenizer(br.readLine());
px = Integer.parseInt(st.nextToken());
py = Integer.parseInt(st.nextToken());
points[i] = new Point(px,py);
}

    pq = new PriorityQueue<>(new Comparator<Edge>() {
        @Override
        public int compare(Edge o1, Edge o2) {
            return Double.compare(o1.dist,o2.dist);
        }
    });
    hasAdd = new boolean[points.length][points.length];
    for(int i = 1;i<points.length;i++){
        for(int j = 1;j<points.length;j++){
            if(i == j){
                continue;
            }
            if(hasAdd[i][j]){
                continue;
            }
            hasAdd[i][j] = hasAdd[j][i] = true;
            pq.add(new Edge(i,j,getDist(points[i],points[j])));
        }
    }
    ans = new PriorityQueue<>(new Comparator<Edge>() {
        @Override
        public int compare(Edge o1, Edge o2) {
            return Double.compare(o2.dist,o1.dist);
        }
    });
    Edge pollEdge;
    while(!pq.isEmpty()){
        if(ans.size()==P-1){
            break;
        }
        pollEdge = pq.poll();
        if(!connect(pollEdge.start,pollEdge.end)){
            union(pollEdge.start,pollEdge.end);
            ans.add(pollEdge);
        }
    }
    for(int i =1;i<S;i++){
        ans.poll();
    }
    double ansDist = Math.sqrt(ans.peek().dist);
    System.out.printf("%.2f",ansDist);
}

private static double getDist(Point x,Point y){
    return Math.pow(x.x-y.x,2)+Math.pow(x.y-y.y,2);
}

static class Edge{
    int start;
    int end;
    double dist;

    public Edge(int start, int end, double dist) {
        this.start = start;
        this.end = end;
        this.dist = dist;
    }
}

static class Point{
    int x;
    int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

private static void init(int N){
    pointIdx = new int[N+1];
    level = new int[N+1];
    for(int i = 0;i<=N;i++){
        pointIdx[i] = i;
    }
}

private static int find(int a){
    if(pointIdx[a] == a){
        return pointIdx[a];
    }
    level[a]++;
    return pointIdx[a] = find(pointIdx[a]);
}

private static void union(int a,int b){
    level[a]=0;
    level[b]=0;
    int A = find(a);
    int B = find(b);
    if(A!=B){
        if(level[a]>level[B]){
            pointIdx[B] = A;
        }
        else{
            pointIdx[A]=B;
        }
    }
}

private static boolean connect(int a,int b){
    return find(a) == find(b);
}

}