Advertisement
Guest User

Untitled

a guest
Mar 23rd, 2018
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.62 KB | None | 0 0
  1.  
  2. import java.util.*;
  3.  
  4. class Vertex{
  5. int x;
  6. int y;
  7. int depth;
  8. Vertex parent;
  9.  
  10. public Vertex (int x, int y) {
  11. this.x = x;
  12. this.y = y;
  13. depth = 0;
  14. parent = this;
  15. }
  16. }
  17.  
  18.  
  19. //class Length implements Comparable<Length> {
  20. class Length{
  21. Vertex u;
  22. Vertex v;
  23. double len;
  24.  
  25. Length(Vertex u, Vertex v, double len) {
  26. this.len = len;
  27. this.u = u;
  28. this.v = v;
  29. }
  30.  
  31. public static Vertex Find(Vertex x) {
  32. if (x.parent == x)
  33. return x;
  34. return Find(x.parent);
  35. }
  36. public static void Union(Vertex x, Vertex y) {
  37. Vertex rootX = Length.Find(x);
  38. Vertex rootY = Length.Find(y);
  39. if (rootX.depth < rootY.depth)
  40. rootX.parent = rootY;
  41. else {
  42. rootY.parent = rootX;
  43. if (rootX.depth == rootY.depth && rootX != rootY)
  44. rootX.depth++;
  45. }
  46. }
  47.  
  48. }
  49.  
  50. public class Kruskal {
  51.  
  52. /*public static Vertex ExtractMin( PriorityQueue<Length> q) {
  53.  
  54. Vertex ptr = q.heap[0];
  55. if (ptr.x == 0)
  56. System.out.println("panic");
  57. q.count--;
  58. if(q.count > 0) {
  59. q.heap[0] = q.heap[q.count];
  60. q.heap[0].index = 0;
  61. //Heapify(0,q.count,q.heap);
  62. }
  63. return ptr;
  64. }
  65. */
  66.  
  67. public double SpanningTree(PriorityQueue<Length> q) {
  68. double E = 0;
  69. for (Length i : q) {
  70. if (Length.Find(i.u) != Length.Find(i.v)) {
  71. E = E + i.len;
  72. Length.Union(i.u, i.v);
  73. }
  74. }
  75. return E;
  76. }
  77.  
  78. public double MST_Kruskal(PriorityQueue<Length> q) {
  79. //ExtractMin(q);
  80. return SpanningTree(q);
  81. }
  82. public static int N;
  83.  
  84. public static void main(String[] args) {
  85. Scanner in = new Scanner(System.in);
  86. int x, y;
  87. N = in.nextInt();
  88.  
  89. Vertex[] g = new Vertex[N];
  90. PriorityQueue<Length> q = new PriorityQueue<>(1000);
  91.  
  92. for ( int i = 0; i < N; i++) {
  93. x = in.nextInt();
  94. y = in.nextInt();
  95. g[i] = new Vertex(x,y);
  96. }
  97.  
  98. for ( int i = 0; i < N; i++) {
  99. for (int j = i + 1; j < N; j++) {
  100. double length = Math.sqrt((g[i].x - g[j].x)*(g[i].x - g[j].x) + (g[i].y - g[j].y)*(g[i].y - g[j].y));
  101. q.add(new Length(g[i], g[j], length));
  102. //g[i].lists.add(j);
  103. }
  104. }
  105.  
  106. Kruskal k = new Kruskal();
  107. double a = k.MST_Kruskal(q);
  108. System.out.printf("%.2f",a);
  109.  
  110. }
  111. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement