Advertisement
Guest User

Untitled

a guest
Mar 30th, 2015
208
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.79 KB | None | 0 0
  1. import java.util.Scanner;
  2. import java.lang.Math;
  3.  
  4. class Point{
  5. int x,y;
  6. }
  7. class Edge{
  8. double l;
  9. int x,y;
  10. }
  11. class KTree{
  12. int parent,rank;
  13. }
  14.  
  15. public class Kruskal {
  16. //static Edge e;
  17. static Edge[] E;
  18. static Point[] P;
  19. static KTree[] T;
  20. static int length;
  21. public static void union(int a,int b){
  22. int c;
  23. if (T[a].rank > T[b].rank){
  24. c = a;
  25. a = b;
  26. b = c;
  27. }
  28. else if (T[a].rank != T[b].rank){
  29. T[a].parent = b;
  30. }
  31. else if (T[a].rank == T[b].rank) {
  32. T[b].rank++;
  33. }
  34. T[a].parent = b;
  35. }
  36. public static int find(int a){
  37. if (a == T[a].parent) {
  38. return a;
  39. }
  40. return T[a].parent = find(T[a].parent);
  41. }
  42. public static void heapify(int a) {
  43. int i;
  44. i = a;
  45. Edge c;
  46. if (2*a<length) {
  47. if (E[a].l>E[2*a].l) {
  48. i=2*a;
  49. }
  50. }
  51. if (2*a+1<length) {
  52. if (E[i].l>E[a*2+1].l) {
  53. i=2*a+1;
  54. }
  55. }
  56. if (i>a) {
  57. c=E[i];
  58. E[i]=E[a];
  59. E[a]=c;
  60. a=i;
  61. heapify(a);
  62. }
  63. // System.out.println("!!!");
  64. }
  65. public static void delete(){
  66. E[0]=E[length-1];
  67. length--;
  68. heapify(0);
  69. // System.out.println("!");
  70. }
  71. public static double SpanningTree(int n){
  72. int i,k;
  73. double sum=0.0;
  74. for (i=length/2; i>=0; i--) {
  75. heapify(i);
  76. }
  77. // System.out.println("!!");
  78. for (k=0;k!=n-1;) {
  79. if (find(E[0].x)!=find(E[0].y)) {
  80. union(find(E[0].x),find(E[0].y));
  81. sum += E[0].l;
  82. k++;
  83. }
  84. delete();
  85. }
  86. return sum;
  87. }
  88.  
  89. public static void main(String[] args) {
  90. Scanner in = new Scanner(System.in);
  91. int n = in.nextInt();
  92. int i,j;
  93. //Edge e=new Edge();
  94. P = new Point[n];
  95. E = new Edge[(n*n-n)/2];
  96. T = new KTree[n];
  97. length=(n*n-n)/2;
  98. int k=0;
  99. double sumMin;
  100. for (i=0;i<n;i++) {
  101. T[i]=new KTree();
  102. P[i]=new Point();
  103. T[i].parent = i;
  104. P[i].x=in.nextInt() ;
  105. P[i].y=in.nextInt() ;
  106. for (j=i-1;j>=0;j--) {
  107. Edge e=new Edge();
  108. e.l = Math.sqrt(((double)(P[i].x-P[j].x)*(P[i].x-P[j].x)+(P[i].y-P[j].y)*(P[i].y-P[j].y)));
  109. e.x=j;
  110. e.y=i;
  111. E[k] = e;
  112. k++;
  113. }
  114. }
  115. sumMin=SpanningTree(n);
  116. System.out.printf("%.2f",sumMin);
  117. }
  118. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement