M-Judge 10157 Save your cats

ACM-ICPC JAG Summer Camp 2010, Day 4
Problem C: Save your cats
より

import java.util.*;
import java.lang.*;
import java.math.*;

public class Main{

    Scanner sc=new Scanner(System.in);

    int n, m;
    int[] x, y;

    int INF=1>>28;

    int[] p;
    int[] rank;

    void run(){
        n=sc.nextInt();
        m=sc.nextInt();
        x=new int[n];
        y=new int[n];

        for(int i=0; i<n; i++){
            x[i]=sc.nextInt();
            y[i]=sc.nextInt();
        }

        double sumW=0.0;
        E[] es=new E[m];
        for(int i=0; i<m; i++){
            int p=sc.nextInt()-1;
            int q=sc.nextInt()-1;
            double w=Math.sqrt((x[q]-x[p])*(x[q]-x[p])+(y[q]-y[p])*(y[q]-y[p]));
            sumW+=w;
            es[i]=new E(p, q, w);
        }

        Arrays.sort(es, new Comparator<E>(){
            public int compare(E e1, E e2){
                return e1.w<e2.w?1:-1;
            }
        });

        p=new int[n];
        rank=new int[n];
        for(int i=0; i<n; i++)
            p[i]=i;

        double extW=0.0;
        for(E e : es){
            if(findSet(e.v)!=findSet(e.u)){
                extW+=e.w;
                union(e.v, e.u);
            }
        }
        println((sumW-extW)+"");
    }

    void union(int x, int y){
        x=findSet(x);
        y=findSet(y);
        if(rank[x]>rank[y]){
            p[y]=x;
        }else{
            p[x]=y;
            if(rank[x]==rank[y]){
                rank[y]++;
            }
        }
    }

    int findSet(int x){
        if(p[x]!=x)
            p[x]=findSet(p[x]);
        return p[x];
    }

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

    void println(String s){
        System.out.println(s);
    }

    void print(String s){
        System.out.print(s);
    }

    class E{
        int v, u;
        double w;

        E(int v, int u, double w){
            this.v=v;
            this.u=u;
            this.w=w;
        }
    }
}

ただし，実行時間3:00[s]超．