Advertisement
Guest User

Untitled

a guest
Mar 22nd, 2018
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.69 KB | None | 0 0
  1.  
  2. import java.io.PrintWriter;
  3. import java.util.*;
  4.  
  5. class Vertex{
  6. int x;
  7. int y;
  8. int depth;
  9. Vertex parent;
  10. // ArrayList<Integer> lists;
  11.  
  12. public Vertex () {
  13. // lists = new ArrayList<>();
  14. depth = 0;
  15. parent = this;
  16. }
  17. }
  18.  
  19. class Len implements Comparable<Len>{
  20. double len;
  21. int n;
  22. Vertex u;
  23. Vertex v;
  24.  
  25. public Len(Vertex u, Vertex v) {
  26. this.v = v;
  27. this.u = u;
  28. this.len = Math.sqrt((u.x - v.x)*(u.x - v.x) + (u.y - v.y)*(u.y - v.y));
  29. }
  30.  
  31. @Override
  32. public int compareTo(Len obj) {
  33. int compare = 0;
  34. if (this.len > obj.len)
  35. compare = 1;
  36. else if (this.len < obj.len)
  37. compare = -1;
  38. return compare;
  39. }
  40.  
  41. }
  42.  
  43. public class Kruskal {
  44.  
  45. private Vertex Find(Vertex x) {
  46. Vertex root;
  47. if (x.parent == x)
  48. root = x;
  49. else {
  50. x.parent = Find(x.parent);
  51. root = x.parent;
  52. }
  53. return root;
  54. }
  55.  
  56.  
  57.  
  58. private void Union(Vertex x, Vertex y) {
  59. Vertex rootX = Find(x);
  60. Vertex rootY = Find(y);
  61. if (rootX.depth < rootY.depth)
  62. rootX.parent = rootY;
  63. else {
  64. rootY.parent = rootX;
  65. if (rootX.depth == rootY.depth && rootX != rootY)
  66. rootX.depth++;
  67. }
  68. }
  69.  
  70. private double SpanningTree(Len[] e) {
  71. double E = 0;
  72. int i = 0;
  73. while (i < e.length) {
  74. Vertex v = e[i].v;
  75. Vertex u = e[i].u;
  76. if (Find(u) != Find(v)) {
  77. E = E + e[i].len;
  78. Union(u, v);
  79. }
  80. i++;
  81. }
  82. return E;
  83. }
  84.  
  85. private void MST_Kruskal(Len[] e) {
  86.  
  87. PrintWriter pw = new PrintWriter(System.out,false);
  88. Arrays.sort(e);
  89. double a;
  90. a = SpanningTree(e);
  91. //return a;
  92. pw.printf("%.2f", a);
  93. pw.close();
  94. }
  95.  
  96. public static void main(String[] args) {
  97. int N, x, y;
  98. Scanner in = new Scanner(System.in);
  99. N = in.nextInt();
  100. int M = N * N / 2;
  101. Vertex[] g = new Vertex[N];
  102. Len[] l = new Len[M];
  103.  
  104. // for (int i = 0; i < N; i++)
  105. // g[i] = new Vertex();
  106.  
  107. if(N == 1) {
  108. for (int i = 0; i < N; i++) {
  109. g[i] = new Vertex();
  110. x = in.nextInt();
  111. y = in.nextInt();
  112. //g[i].lists.add(y);
  113. //g[i].lists.add(x);
  114. g[i].x = x;
  115. g[i].y = y;
  116. }
  117.  
  118. int ind = 0;
  119. /* for (int i = 0; i < M; i++)
  120. l[i] = new Len(g[0], g[0]);*/
  121. for (int i = 0; i < N; i++) {
  122. for (int j = i + 1; j < N; j++) {
  123. l[ind++] = new Len(g[i], g[j]);
  124. }
  125. }
  126. }
  127. else{
  128. for (int i = 0; i < N; i++) {
  129. g[i] = new Vertex();
  130. l[i] = new Len(g[0],g[0]);
  131. x = in.nextInt();
  132. y = in.nextInt();
  133. //g[i].lists.add(y);
  134. //g[i].lists.add(x);
  135. g[i].x = x;
  136. g[i].y = y;
  137. }
  138.  
  139. int ind = 0;
  140. for (int i = N; i < M; i++)
  141. l[i] = new Len(g[0], g[0]);
  142. for (int i = 0; i < N; i++) {
  143. for (int j = i + 1; j < N; j++) {
  144. l[ind++] = new Len(g[i], g[j]);
  145. //System.out.println(ind++);
  146. }
  147. }
  148. }
  149.  
  150. Kruskal k = new Kruskal();
  151. k.MST_Kruskal(l);
  152. }
  153. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement