Source code for submission s917

Spider.java

  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. class Spider {
  5.  
  6. //private static final boolean DEBUG = true;
  7.  
  8. public static void main( String[] args ) throws Exception {
  9. String line = br.readLine();
  10. String[] p;
  11. while ( line != null ) {
  12. p = line.split( " " );
  13. int n = toi( p[0] );
  14. int m = toi( p[1] );
  15. Edge[] es = new Edge[m];
  16. int[] v2c = new int[n];
  17. LinkedList<Integer>[] c2v = new LinkedList[n];
  18. int c = n; // components count
  19. for ( int i = 0; i < n; ++i ) { v2c[i] = i; c2v[i] = new LinkedList<Integer>(); c2v[i].add(i); }
  20.  
  21. for ( int i = 0; i < m; ++i ) {
  22. p = br.readLine().split(" ");
  23. es[i] = new Edge( toi(p[0]) - 1, toi(p[1]) - 1, toi(p[2]) );
  24. }
  25.  
  26. Arrays.sort( es ); // sort by len
  27.  
  28. Edge last = es[es.length-1];
  29. long sum = -last.len;
  30. int fc, tc;
  31. fc = v2c[last.from]; // from component
  32. tc = v2c[last.to]; // to component
  33. for ( Integer v : c2v[tc] ) {
  34. v2c[v] = fc;
  35. c2v[fc].add( v );
  36. }
  37. c2v[tc] = null;
  38. --c;
  39.  
  40. for ( int i = 0; i < m; ++i ) {
  41. fc = v2c[es[i].from]; // from component
  42. tc = v2c[es[i].to]; // to component
  43. if ( fc == tc ) continue; // already connected
  44. //if (DEBUG) System.out.println( String.format( "DEBUG: joining %d %d", fc, tc ) );
  45.  
  46. sum += es[i].len;
  47. // join components
  48. for ( Integer v : c2v[tc] ) {
  49. v2c[v] = fc;
  50. c2v[fc].add( v );
  51. }
  52. c2v[tc] = null;
  53. --c;
  54. }
  55.  
  56. if ( c > 1 ) System.out.println( "disconnected" );
  57. else System.out.println( sum );
  58.  
  59. line = br.readLine();
  60. }
  61. }
  62.  
  63. static class Edge implements Comparable<Edge> {
  64. int from; int to; long len;
  65.  
  66. Edge( int f, int t, int l ) { from = f; to = t; len = l; }
  67.  
  68. public int compareTo( Edge e ) {
  69. if ( this.len == e.len ) return 0;
  70. return this.len < e.len ? -1 : 1;
  71. }
  72.  
  73. }
  74.  
  75. private static final int toi( String s ) { return Integer.parseInt(s); }
  76.  
  77. }
  78.