Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.util.ArrayList;
- public class Kruskal {
- private static ArrayList<Triplet> edge;
- private static int[] group;
- private static double weight;
- public static class Triplet {
- public int x;
- public int y;
- public double z;
- Triplet(int x, int y, double z) {
- this.x=x;
- this.y=y;
- this.z=z;
- }
- }
- public static class Pair {
- public int x;
- public int y;
- Pair (int x, int y) {
- this.x=x;
- this.y=y;
- }
- }
- private static void qsort(ArrayList<Triplet> arr, int start, int end) {
- if (start >= end)
- return;
- int i = start;
- int k = end;
- double mid = arr.get((i + k) / 2).z;
- while (i <= k) {
- while (arr.get(i).z < mid && i <= end)
- i++;
- while (arr.get(k).z > mid && k >= start)
- k--;
- if (i <= k) {
- double tmpL = arr.get(i).z;
- arr.get(i).z = arr.get(k).z;
- arr.get(k).z = tmpL;
- int tmp = arr.get(i).x;
- arr.get(i).x = arr.get(k).x;
- arr.get(k).x = tmp;
- int tmp1 = arr.get(i).y;
- arr.get(i).y = arr.get(k).y;
- arr.get(k).y = tmp1;
- i++;
- k--;
- }
- }
- qsort(arr, start, k);
- qsort(arr, i, end);
- }
- public static void main(String[] args) {
- ArrayList<Pair> coordinate = new ArrayList<>();
- edge = new ArrayList<>();
- Scanner scanner = new Scanner(System.in);
- int N = scanner.nextInt();
- group = new int[N];
- for (int i = 0; i < N; i++) {
- group[i] = i;
- int x = scanner.nextInt(), y = scanner.nextInt();
- coordinate.add(new Pair(x, y));
- }
- for (int i = 0; i < N; i++) {
- for (int j = i + 1; j < N; j++) {
- edge.add(new Triplet(i, j, Math.sqrt((coordinate.get(i).x - coordinate.get(j).x) * (coordinate.get(i).x - coordinate.get(j).x) + (coordinate.get(i).y - coordinate.get(j).y) * (coordinate.get(i).y - coordinate.get(j).y))));
- }
- }
- /*edge.sort((o1, o2) -> {
- if (o1.z > o2.z) return 1;
- else if (o1.z < o2.z) return -1;
- else return 0;
- });*/
- qsort(edge, 0, edge.size() - 1);
- MST_Kruskal();
- System.out.printf("%.2f",weight);
- }
- private static void MST_Kruskal() {
- int c=0;
- int e=0;
- weight=(double)0;
- int a = group.length;
- while (c<a-1) {
- int u1, u2;
- u1=edge.get(e).x;
- u2=edge.get(e).y;
- if(group[u1]!=group[u2]) {
- int m=group[u2];
- c++;
- weight+=edge.get(e).z;
- for(int i=0; i<a; i++)
- if (group[i]==m)
- group[i]=group[u1];
- }
- e++;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement