Guest User

Untitled

a guest
Jul 18th, 2018
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.01 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.FileReader;
  3. import java.io.FileWriter;
  4. import java.io.IOException;
  5. import java.io.PrintWriter;
  6. import java.util.StringTokenizer;
  7. import java.lang.Math;
  8. import java.util.ArrayList;
  9. import java.util.PriorityQueue;
  10.  
  11.  
  12. public class primMain implements Runnable {
  13. StringTokenizer st;
  14. BufferedReader in;
  15. PrintWriter out;
  16. double ans;
  17. static int AAA=2000000000;
  18. //classes
  19. public static class Vertex implements Comparable<Vertex> {
  20. //double d;
  21. boolean visited;
  22. Vertex parent;
  23. long key;
  24. ArrayList<Edge> adj;
  25.  
  26. public int compareTo(Vertex other) {
  27. Vertex ver = (Vertex) other;
  28. return (int) (key - ver.key);
  29. }
  30. public Vertex() {
  31. //d=0;
  32. adj = new ArrayList<Edge>();
  33. key=AAA;
  34. visited=false;
  35. }
  36. }
  37.  
  38. public static class Edge {
  39. Vertex v1, v2;
  40. long weight;
  41. }
  42. /////////////
  43. //variables//
  44. /////////////
  45. int n;
  46. long x[];
  47. long y[];
  48. Vertex vertexes[];
  49. PriorityQueue<Vertex> que = new PriorityQueue<Vertex>();
  50.  
  51. public static void main(String[] args) {
  52. new Thread(new primMain()).run();
  53. }
  54.  
  55. public void run() {
  56. try {
  57. in = new BufferedReader(new FileReader("spantree.in"));
  58. out = new PrintWriter(new FileWriter("spantree.out"));
  59. solve();
  60. } catch (Exception e) {
  61. e.printStackTrace();
  62. } finally {
  63. out.flush();
  64. out.close();
  65. }
  66. }
  67.  
  68. String nextToken() throws IOException {
  69. while (st == null || !st.hasMoreTokens()) {
  70. st = new StringTokenizer(in.readLine());
  71. }
  72. return st.nextToken();
  73. }
  74.  
  75. int nextInt() throws NumberFormatException, IOException {
  76. return Integer.parseInt(nextToken());
  77. }
  78.  
  79. long nextLong() throws NumberFormatException, IOException {
  80. return Long.parseLong(nextToken());
  81. }
  82.  
  83. double nextDouble() throws NumberFormatException, IOException {
  84. return Double.parseDouble(nextToken());
  85. }
  86. void Prim (){
  87.  
  88. vertexes[0].key=0;
  89.  
  90. que.add(vertexes[0]);
  91.  
  92.  
  93. while (!que.isEmpty()) {
  94. Vertex u;
  95.  
  96. u=new Vertex();
  97. u=que.remove();
  98. u.visited=true;
  99. int s=u.adj.size();
  100. Vertex v;
  101. v=new Vertex();
  102. Edge e;
  103. e=new Edge();
  104. Vertex vv;
  105. vv=new Vertex();
  106. for (int i=0; i<s;i++ ){
  107. e=u.adj.get(i);
  108. v=e.v2;
  109. if (/*(que.contains(v)) &&*/ (e.weight < v.key)&&(v.visited==false)) {
  110. v.parent=u;
  111. v.key=e.weight;
  112. vv=v;
  113. }
  114. }
  115. que.add(v);
  116.  
  117.  
  118.  
  119. }
  120. }
  121. void solve() throws NumberFormatException, IOException {
  122. n = nextInt();
  123. x = new long[n];
  124. y = new long[n];
  125. vertexes = new Vertex[n];
  126. for (int i = 0; i < n; i++) {
  127. x[i] = nextLong();
  128. y[i] = nextLong();
  129. vertexes[i]=new Vertex();
  130.  
  131. }
  132. for (int i = 0; i < n; i++) {
  133. for (int j = 0; j < n; j++) {
  134. long w =((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
  135. Edge e;
  136. e = new Edge();
  137. e.v1=vertexes[i];
  138. e.v2=vertexes[j];
  139. e.weight=w;
  140. vertexes[i].adj.add(e);
  141. }
  142. }
  143. Prim();
  144. for (int i=0;i<n; i++) {
  145. ans+=Math.sqrt(vertexes[i].key);
  146. }
  147. out.println(ans);
  148.  
  149. }
  150. }
Add Comment
Please, Sign In to add comment