The Java Program: Cables.java

  1 /*
  2   Southeast USA, 2010.  Problem J: Underground Cables
  3   Categories: Euclidean minimum spanning tree, Prim's algorithm
  4  */
  5 
  6 import java.io.*;
  7 import java.util.Scanner;
  8 import java.util.Arrays;
  9 
 10 /*
 11   Euclidean minimum spanning tree; minimum spanning tree in a complete,
 12   undirected graph with weights equal to the Eucledian distance
 13   between the points.
 14 
 15   Prim's algorithm.  We maintain a cut of graph comprisng of MST vertices
 16   and those not yet chosen.  We add the minimum crossing edge.  O(N*N)
 17 
 18   The minimum spanning tree in a Euclidean graph does not have
 19   intersecting edges.  For suppose that it did.  Drop the two
 20   intersecting edges.  Only two of the four incident nodes are remain
 21   connected.  Connect them withour crossing to the other two nodes.
 22   The graph becomes reconnect and no cyles are introduces (we have a
 23   spanning tree).  The edges are shorted by the triangle inequality.
 24 */
 25 
 26 public final class Cables {
 27 
 28    private static final Scanner STDIN =
 29       new Scanner (new BufferedInputStream (System.in));
 30 
 31    public static void main (final String[] args) {
 32 
 33       input: for (int ds=1; /**/; ds++) {
 34          final int n = STDIN.nextInt();
 35          if (n==0) break;
 36          assert 2<=n && n<=1000;
 37 
 38          int[] x=new int[n], y=new int[n];
 39          double[] cost=new double[n]; // distance to MST
 40          boolean[] visit=new boolean [n];
 41 
 42          for (int i=0; i<n; i++) {
 43             x[i] = STDIN.nextInt();  assert -1000<=x[i] && x[i]<=1000;
 44             y[i] = STDIN.nextInt();  assert -1000<=y[i] && y[i]<=1000;
 45          }
 46 
 47          Arrays.fill (cost, Double.MAX_VALUE);
 48          cost[0]=0.0D;
 49          double total = 0.0;
 50          for (int i=0; i<cost.length; i++) {
 51             // Find next node to visit: minimum distance to MST
 52             double m=Double.MAX_VALUE; int v=-1;
 53             for (int j=0; j<cost.length; j++) {
 54                if (!visit[j] && cost[j]<m) { v=j; m=cost[j]; }
 55             }
 56             visit[v]=true;
 57             total+= m;
 58             for (int j=0; j<cost.length; j++) {
 59                final double d = Math.hypot (x[v]-x[j],y[v]-y[j]);
 60                if (d<cost[j]) cost[j]=d;
 61             }
 62          }
 63          System.out.format ("%.2f", total);
 64       }
 65    }
 66 }
 67 
 68 /*
 69  * ------------For GNU Emacs ------------
 70  * Local Variables:
 71  * compile-command: "javac Cables.java"
 72  * End:
 73  */