Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.*;
- import java.util.*;
- /**
- * Created with IntelliJ IDEA.
- * User: yulya3102
- * Date: 11/11/12
- * Time: 12:55 AM
- * To change this template use File | Settings | File Templates.
- */
- public class A {
- public static void main(String[] args) throws IOException {
- BufferedReader in = new BufferedReader(new FileReader("spantree.in"));
- StringTokenizer str = new StringTokenizer(in.readLine());
- int n = Integer.parseInt(str.nextToken());
- Graph graph = new Graph(n);
- for (int i = 0; i < n; i++) {
- str = new StringTokenizer(in.readLine());
- int x = Integer.parseInt(str.nextToken());
- int y = Integer.parseInt(str.nextToken());
- graph.add(x, y);
- }
- PrintWriter out = new PrintWriter(new File("spantree.out"));
- out.print(graph.prim(0));
- out.close();
- }
- private static class Graph {
- private class Dot {
- public int x, y;
- public Dot(int x, int y) {
- this.x = x;
- this.y = y;
- }
- }
- private int n;
- ArrayList<Dot> dots;
- public Graph(int n) {
- this.n = n;
- dots = new ArrayList<Dot>(n);
- }
- public void add(int x, int y) {
- dots.add(new Dot(x, y));
- }
- private class Node {
- public int v;
- public double key;
- public Node(int v, double key) {
- this.v = v;
- this.key = key;
- }
- }
- private double w(Dot a, Dot b) {
- return Math.sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
- }
- public double prim(int r) {
- double result = 0;
- double key[] = new double[n];
- boolean f[] = new boolean[n];
- for (int i = 0; i < n; i++)
- key[i] = Integer.MAX_VALUE;
- key[r] = 0;
- PriorityQueue<Node> queue = new PriorityQueue<Node>(n, new Comparator<Node>() {
- @Override
- public int compare(Node o1, Node o2) {
- if (o1.key > o2.key)
- return 1;
- if (o1.key < o2.key)
- return -1;
- return 0;
- }
- });
- for (int i = 0; i < n; i++)
- queue.add(new Node(i, key[i]));
- Node node = null;
- while (!queue.isEmpty()) {
- node = queue.poll();
- if (node.key == key[node.v]) {
- int u = node.v;
- f[u] = true;
- for (int v = 0; v < n; v++) {
- if (v != u) {
- double weight = w(dots.get(v), dots.get(u));
- if ((!f[v]) && (weight < key[v])) {
- key[v] = weight;
- queue.add(new Node(v, key[v]));
- }
- }
- }
- }
- }
- for (int i = 0; i < n; i++)
- result += key[i];
- return result;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment