SeoSeungjun/baekjoon_1774.java at main · KB-JACOS/SeoSeungjun · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
import java.util.*;
import java.io.*;

public class baekjoon_1774 {

    static int[] root, rank;
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        rank = new int[N+1];
        root = new int[N+1];

        PriorityQueue<God> pq = new PriorityQueue<>((o1, o2) -> Double.compare(o1.w, o2.w));

        List<int[]> gods = new ArrayList<>();
        gods.add(new int[]{-1, -1});
        for(int i=1;i<=N;i++) {
            root[i] = i;
            st= new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            gods.add(new int[]{x, y});
        }

        boolean[][] connected = new boolean[N+1][N+1];
        for(int i=0;i<M;i++ ) {
            st = new StringTokenizer(br.readLine());

            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            connected[s][e] = true;
            connected[e][s] = true;

            pq.add(new God(s, e, 0));
        }

        for(int i=1;i<=N;i++) {
            for(int j=i;j<=N;j++) {

                if(connected[i][j]) continue;

                int[] a = gods.get(i);
                int[] b = gods.get(j);

                double distance = Math.sqrt(Math.pow(a[0] - b[0], 2) + Math.pow(a[1] - b[1], 2));
                pq.add(new God(i, j, distance));
            }
        }

        double cnt = 0;
        while(!pq.isEmpty()) {

            God cur = pq.poll();

            int rootA = find(cur.a);
            int rootB = find(cur.b);

            if(rootA != rootB)  {
                union(cur.a, cur.b);
                cnt += cur.w;
            }
        }

        System.out.printf("%.2f\n", cnt);


    }

    static class God {
        int a, b;
        double w;

        public God(int a, int b, double w) {
            this.a = a;
            this.b = b;
            this.w = w;
        }
    }

    public static void union(int a, int b) {

        int rootA = root[a];
        int rootB = root[b];

        if(rootA == rootB) return;

        if(rank[rootA] < rank[rootB]) {
            root[rootA] = rootB;
        }
        else if(rank[rootA] > rank[rootB]) {
            root[rootB] = rootA;
        }
        else {
            root[rootB] = rootA;
            rank[rootA]++;
        }

    }

    public static int find(int num) {
        if(root[num] != num) {
            root[num] = find(root[num]);
        }

        return root[num];
    }

}