Advertisement
Guest User

Untitled

a guest
Sep 25th, 2017
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.11 KB | None | 0 0
  1. import java.util.*;
  2. import java.util.ArrayList;
  3.  
  4.  
  5. public class Kruskal {
  6. private static ArrayList<Triplet> edge;
  7. private static int[] group;
  8. private static double weight;
  9. public static class Triplet {
  10. public int x;
  11. public int y;
  12. public double z;
  13. Triplet(int x, int y, double z) {
  14. this.x=x;
  15. this.y=y;
  16. this.z=z;
  17. }
  18. }
  19.  
  20. public static class Pair {
  21. public int x;
  22. public int y;
  23. Pair (int x, int y) {
  24. this.x=x;
  25. this.y=y;
  26. }
  27. }
  28.  
  29. private static void qsort(ArrayList<Triplet> arr, int start, int end) {
  30. if (start >= end)
  31. return;
  32. int i = start;
  33. int k = end;
  34. double mid = arr.get((i + k) / 2).z;
  35. while (i <= k) {
  36. while (arr.get(i).z < mid && i <= end)
  37. i++;
  38. while (arr.get(k).z > mid && k >= start)
  39. k--;
  40. if (i <= k) {
  41. double tmpL = arr.get(i).z;
  42. arr.get(i).z = arr.get(k).z;
  43. arr.get(k).z = tmpL;
  44. int tmp = arr.get(i).x;
  45. arr.get(i).x = arr.get(k).x;
  46. arr.get(k).x = tmp;
  47. int tmp1 = arr.get(i).y;
  48. arr.get(i).y = arr.get(k).y;
  49. arr.get(k).y = tmp1;
  50. i++;
  51. k--;
  52. }
  53. }
  54. qsort(arr, start, k);
  55. qsort(arr, i, end);
  56. }
  57.  
  58.  
  59. public static void main(String[] args) {
  60. ArrayList<Pair> coordinate = new ArrayList<>();
  61. edge = new ArrayList<>();
  62. Scanner scanner = new Scanner(System.in);
  63. int N = scanner.nextInt();
  64. group = new int[N];
  65. for (int i = 0; i < N; i++) {
  66. group[i] = i;
  67. int x = scanner.nextInt(), y = scanner.nextInt();
  68. coordinate.add(new Pair(x, y));
  69. }
  70.  
  71. for (int i = 0; i < N; i++) {
  72. for (int j = i + 1; j < N; j++) {
  73. 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))));
  74. }
  75. }
  76. /*edge.sort((o1, o2) -> {
  77. if (o1.z > o2.z) return 1;
  78. else if (o1.z < o2.z) return -1;
  79. else return 0;
  80. });*/
  81. qsort(edge, 0, edge.size() - 1);
  82.  
  83.  
  84. MST_Kruskal();
  85. System.out.printf("%.2f",weight);
  86.  
  87. }
  88. private static void MST_Kruskal() {
  89. int c=0;
  90. int e=0;
  91. weight=(double)0;
  92. int a = group.length;
  93. while (c<a-1) {
  94. int u1, u2;
  95. u1=edge.get(e).x;
  96. u2=edge.get(e).y;
  97. if(group[u1]!=group[u2]) {
  98. int m=group[u2];
  99. c++;
  100. weight+=edge.get(e).z;
  101. for(int i=0; i<a; i++)
  102. if (group[i]==m)
  103. group[i]=group[u1];
  104. }
  105. e++;
  106. }
  107. }
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement