yulya3102

5A

Nov 13th, 2012
97
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.25 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. /**
  5.  * Created with IntelliJ IDEA.
  6.  * User: yulya3102
  7.  * Date: 11/11/12
  8.  * Time: 12:55 AM
  9.  * To change this template use File | Settings | File Templates.
  10.  */
  11. public class A {
  12.     public static void main(String[] args) throws IOException {
  13.         BufferedReader in = new BufferedReader(new FileReader("spantree.in"));
  14.         StringTokenizer str = new StringTokenizer(in.readLine());
  15.         int n = Integer.parseInt(str.nextToken());
  16.         Graph graph = new Graph(n);
  17.         for (int i = 0; i < n; i++) {
  18.             str = new StringTokenizer(in.readLine());
  19.             int x = Integer.parseInt(str.nextToken());
  20.             int y = Integer.parseInt(str.nextToken());
  21.             graph.add(x, y);
  22.         }
  23.         PrintWriter out = new PrintWriter(new File("spantree.out"));
  24.         out.print(graph.prim(0));
  25.         out.close();
  26.     }
  27.  
  28.     private static class Graph {
  29.         private class Dot {
  30.             public int x, y;
  31.             public Dot(int x, int y) {
  32.                 this.x = x;
  33.                 this.y = y;
  34.             }
  35.         }
  36.  
  37.         private int n;
  38.         ArrayList<Dot> dots;
  39.  
  40.         public Graph(int n) {
  41.             this.n = n;
  42.             dots = new ArrayList<Dot>(n);
  43.         }
  44.  
  45.         public void add(int x, int y) {
  46.             dots.add(new Dot(x, y));
  47.         }
  48.  
  49.         private class Node {
  50.             public int v;
  51.             public double key;
  52.  
  53.             public Node(int v, double key) {
  54.                 this.v = v;
  55.                 this.key = key;
  56.             }
  57.         }
  58.  
  59.         private double w(Dot a, Dot b) {
  60.             return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
  61.         }
  62.  
  63.         public double prim(int r) {
  64.             double result = 0;
  65.             double key[] = new double[n];
  66.             boolean f[] = new boolean[n];
  67.             for (int i = 0; i < n; i++)
  68.                 key[i] = Integer.MAX_VALUE;
  69.             key[r] = 0;
  70.             PriorityQueue<Node> queue = new PriorityQueue<Node>(n, new Comparator<Node>() {
  71.                 @Override
  72.                 public int compare(Node o1, Node o2) {
  73.                     if (o1.key > o2.key)
  74.                         return 1;
  75.                     if (o1.key < o2.key)
  76.                         return -1;
  77.                     return 0;
  78.                 }
  79.             });
  80.             for (int i = 0; i < n; i++)
  81.                 queue.add(new Node(i, key[i]));
  82.             Node node = null;
  83.             while (!queue.isEmpty()) {
  84.                 node = queue.poll();
  85.                 if (node.key == key[node.v]) {
  86.                     int u = node.v;
  87.                     f[u] = true;
  88.                     for (int v = 0; v < n; v++) {
  89.                         if (v != u) {
  90.                             double weight = w(dots.get(v), dots.get(u));
  91.                             if ((!f[v]) && (weight < key[v])) {
  92.                                 key[v] = weight;
  93.                                 queue.add(new Node(v, key[v]));
  94.                             }
  95.                         }
  96.                     }
  97.                 }
  98.             }
  99.             for (int i = 0; i < n; i++)
  100.                 result += key[i];
  101.             return result;
  102.         }
  103.     }
  104. }
Advertisement
Add Comment
Please, Sign In to add comment