import java.io.*; import java.util.*; import java.awt.*; /** * Solution to Tsunami * * @author vanb */ public class tsunami { public Scanner sc; public PrintStream ps; /** * This will hold the parameters of a cable: an index of eacg * of the two endpoints, and its length. */ public class Cable implements Comparable { public int a, b; public double distance; /** * Create a Cable * @param a Index of an endpoint * @param b Index of the other endpoint * @param distance Length */ public Cable( int a, int b, double distance ) { this.a = a; this.b = b; this.distance = distance; } /** * Compare two Cables by distance. * * @param c Cable to compare to this Cable * @return -1, 0 or 1, just like a standard compareTo method. */ public int compareTo( Cable c ) { return Double.compare( distance, c.distance ); } /** * Produce a pretty string for debugging. */ public String toString() { return "{a=" + a + ", b=" + b + ", distance=" + distance + "}"; } } // The link[] array will help us manage the sets we'll use // for Kruskal's MST algorithm. public int parent[] = new int[1000]; // This is the minimum y value of a set of cities public int miny[] = new int[1000]; /** * Figure out which set city i is in. * * We'll maintain each set as a tree, with each node linked to its parent. * We'll use the index of the root node of the tree as a unique identifier * for the set. * * @param i City index * @return Indicates which set i is in. */ public int set( int i ) { // Find the root (that's where parent[i]==-1) while( parent[i]>=0 ) i=parent[i]; return i; } /** * Merge the set that i is in with the set that j is in. * * @param i City * @param j Another city */ public void merge( int i, int j ) { // Get the root of i's tree, which identifies its set i = set(i); // Look for the root of j's tree while( parent[j]>=0 ) { int t = j; j = parent[j]; // On our way up, we'll do some surgery on the tree. // We'll point these nodes directly to the root. // We're only interested in the root anyway, so this // does no harm, and it can speed us up if we come looking // for one of these nodes later. parent[t] = i; } // Put this subtree under i parent[j] = i; // The minimum y of this new merged set is // the minimum of the y's of the two sets we're merging miny[i] = Math.min( miny[i], miny[j] ); } /** * Driver. * @throws Exception */ public void doit(String filename) throws Exception { sc = new Scanner( new File( filename ) ); ps = System.out; //new PrintStream( new FileOutputStream( "tsunami.out" ) ); Point cities[] = new Point[1000]; PriorityQueue queue = new PriorityQueue(); // We'll use a modification of Kruskal's algorithm to find a // Minimum Spanning Tree. // // Kruskal's algorithm goes like this: Start with each node in its own set. // If you've got n nodes, then you've got n sets. Then, sort all of // edges by weight (in this case, length or distance) Go through the edges, // smallest to largest. If an edge connects two nodes that are in difference sets, // then union those two sets, and add that edge to the Minimum Spanning Tree. // (Obviously, if the two nodes are in the same set, then we don't need that edge. // Just pass it by.) That's all there is to it! for(;;) { int n = sc.nextInt(); if( n==0 ) break; // At the beginning, every city is in its own set. Arrays.fill( parent, -1 ); for( int i=0; i cities[b].y ) { ok = oka; } // Ditto for b. else if(cities[a].y < cities[b].y) { ok = okb; } // If they're equal, then using this edge is OK if either a or b is OK. else { ok = oka || okb; } // If OK, use this edge. if( ok ) { // Merge the sets, record the distance. merge( a, b ); total += cable.distance; } } } ps.printf( "%.02f", total ); ps.println(); } } /** * @param args */ public static void main( String[] args ) throws Exception { new tsunami().doit(args[0]); } }