daily pastebin goal
68%
SHARE
TWEET

Untitled

a guest Jul 18th, 2018 59 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top