M-Judge 10157 Save your cats

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

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4.   
5. public class Main{  
6.   
7.     Scanner sc=new Scanner(System.in);  
8.   
9.     int n, m;  
10.     int[] x, y;  
11.   
12.     int INF=1>>28;  
13.   
14.     int[] p;  
15.     int[] rank;  
16.   
17.     void run(){  
18.         n=sc.nextInt();  
19.         m=sc.nextInt();  
20.         x=new int[n];  
21.         y=new int[n];  
22.   
23.         for(int i=0; i<n; i++){  
24.             x[i]=sc.nextInt();  
25.             y[i]=sc.nextInt();  
26.         }  
27.   
28.         double sumW=0.0;  
29.         E[] es=new E[m];  
30.         for(int i=0; i<m; i++){  
31.             int p=sc.nextInt()-1;  
32.             int q=sc.nextInt()-1;  
33.             double w=Math.sqrt((x[q]-x[p])*(x[q]-x[p])+(y[q]-y[p])*(y[q]-y[p]));  
34.             sumW+=w;  
35.             es[i]=new E(p, q, w);  
36.         }  
37.   
38.         Arrays.sort(es, new Comparator<E>(){  
39.             public int compare(E e1, E e2){  
40.                 return e1.w<e2.w?1:-1;  
41.             }  
42.         });  
43.   
44.         p=new int[n];  
45.         rank=new int[n];  
46.         for(int i=0; i<n; i++)  
47.             p[i]=i;  
48.   
49.         double extW=0.0;  
50.         for(E e : es){  
51.             if(findSet(e.v)!=findSet(e.u)){  
52.                 extW+=e.w;  
53.                 union(e.v, e.u);  
54.             }  
55.         }  
56.         println((sumW-extW)+"");  
57.     }  
58.   
59.     void union(int x, int y){  
60.         x=findSet(x);  
61.         y=findSet(y);  
62.         if(rank[x]>rank[y]){  
63.             p[y]=x;  
64.         }else{  
65.             p[x]=y;  
66.             if(rank[x]==rank[y]){  
67.                 rank[y]++;  
68.             }  
69.         }  
70.     }  
71.   
72.     int findSet(int x){  
73.         if(p[x]!=x)  
74.             p[x]=findSet(p[x]);  
75.         return p[x];  
76.     }  
77.   
78.     public static void main(String[] args){  
79.         new Main().run();  
80.     }  
81.   
82.     void println(String s){  
83.         System.out.println(s);  
84.     }  
85.   
86.     void print(String s){  
87.         System.out.print(s);  
88.     }  
89.   
90.     class E{  
91.         int v, u;  
92.         double w;  
93.   
94.         E(int v, int u, double w){  
95.             this.v=v;  
96.             this.u=u;  
97.             this.w=w;  
98.         }  
99.     }  
100. }  

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]超．