import java.io.*; import java.util.*; /** * Solution to Winter Roads. * * @author vanb */ public class bridges2_vanb { public Scanner sc; public PrintStream ps; /** * A Landmark * * @author vanb */ public class Landmark { // All roads to/from this landmark public LinkedList roads = new LinkedList(); // ONLY the roads in the spanning tree public LinkedList tree = new LinkedList(); // Which set this Landmark is in (for the spanning tree algorithm) public int set = 0; // An ID - only used for debugging public int id = 0; /** * Determine if a truck with cargo c can get * from this node to the destination. * * @param dest Destination landmark * @param c Cargo weight of the truck * @param from The road we came from * @return true if the truck can make it, otherwise false */ public boolean cango( Landmark dest, int c, Road from ) { boolean result = false; if( this==dest ) { // We're here! result = true; } else { // Look at all roads in the tree that aren't where we came from, // and which have sufficient capacity for( Road road : tree ) if( road!=from && road.capacity>=c ) { result = road.destination( this ).cango( dest, c, road ); if( result ) break; } } return result; } /** * Change the set of this node and the entire * spanning subtree rooted here * * @param newset New set number * @param from Road we came from * @return Number of landmarks in this set */ public int changeSet( int newset, Road from ) { set = newset; int count = 1; // Start with this one for( Road road : tree ) if( road!=from ) { count += road.destination( this ).changeSet( newset, road ); } return count; } /** * Display the minimum spanning tree rooted at a given road, for debugging. * * @param from Root road */ public void showtree( Road from ) { System.err.println(); System.err.println( "Node " + id ); for( Road road : tree ) { System.err.println( "Road " + road.capacity + " to " + road.destination( this ).id ); } for( Road road : tree ) if( road!=from ) { road.destination( this ).showtree( road ); } } } /** * A Road * * @author vanb */ public class Road implements Comparable { /** How much can this road hold? */ public int capacity; /** Where is this road in the Heap? */ public int index; /** The endpoints of the road */ public Landmark landmark1, landmark2; /** Is this road in the Maximum Spanning Tree? */ public boolean inTree; /** * Get the destination landmark, given the source. * * @param source Source landmark * @return Destination landmark */ public Landmark destination( Landmark source ) { return landmark1==source ? landmark2 : landmark1; } /** * Simple comparison by capacity. It's backwards from * a usual compareTo so the roads will get sorted largest-first. * * @param r Road to compare to * @return -1 if this is bigger than r, 1 if r is bigger than this, 0 if equal. */ public int compareTo( Road r ) { return r.capacity - capacity; } /** * A pretty string for debugging */ public String toString() { return "{Road:from " + landmark1.id + " to " + landmark2.id + " capacity=" + capacity + "}"; } /** * Add this Road to the spanning tree */ public void addToTree() { landmark1.tree.add( this ); landmark2.tree.add( this ); landmark1.changeSet( landmark2.set, null ); inTree = true; } } // A priority queue public PriorityQueue pq = new PriorityQueue(); // Build a heap-o-roads public Road heap[]; /** * Swap two elements of the heap. * * @param i1 Index into the heap * @param i2 Another index into the heap. */ public void swap( int i1, int i2 ) { // Swap elements Road temp = heap[i1]; heap[i1] = heap[i2]; heap[i2] = temp; // Fix indices heap[i1].index = i1; heap[i2].index = i2; } /** * Bubble s Road up in the heap. * * @param road Road to bubble up */ public void bubbleup( int index ) { for(;;) { // In the heap, the node at index has its parent at index/2. int parent = index/2; // if we're at the root (which is at heap[1]), or if the parent is bigger, // then we're done. if( index<=1 || heap[parent].capacity>=heap[index].capacity ) break; // Otherwise, swap this with its parent swap( index, parent ); // And, keep going. index = parent; } } /** * Sink a road down in the heap. * * @param road Road to sink down */ public void sinkdown( int index ) { for(;;) { // In the heap, a node at index has two kids: one at index*2, the other at index*2+1 int kid1 = index*2; int kid2 = kid1+1; // Find the kid we'd like to swap with. // It's the bigger of the two, unless kid2 is off the heap int kid = (kid2>=heap.length || heap[kid1].capacity>heap[kid2].capacity) ? kid1 : kid2; // Check to see if we want to swap. // If the kid is off the heap, or if it's too small, then we're done. if( kid>=heap.length || heap[index].capacity>=heap[kid].capacity ) break; // Swap with the kid swap( index, kid ); // And, keep going. index = kid; } } /** * Do it! * * @throws Exception */ public void doit() throws Exception { sc = new Scanner (System.in); ps = System.out; // Allocate all Landmarks beforehand Landmark landmarks[] = new Landmark[1000]; for( int i=0; i<1000; i++ ) { landmarks[i] = new Landmark(); landmarks[i].id = i+1; } // Ditto Roads Road roads[] = new Road[100000]; for( int i=0; i<100000; i++ ) { roads[i] = new Road(); } for(;;) { int n = sc.nextInt(); int m = sc.nextInt(); if( n==0 ) break; // Clear out the Landmarks to start afresh for( int i=0; i