Source code for submission s960

Go to diff to previous submission

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

Diff to submission s917

Spider.java

--- c4.s917.cteam046.spider.java.0.Spider.java
+++ c4.s960.cteam046.spider.java.0.Spider.java
@@ -14,4 +14,5 @@
                         int n = toi( p[0] );
                         int m = toi( p[1] );
+                        if ( m == 0 ) { System.out.println( "disconnected" ); line = br.readLine(); continue; }
                         Edge[] es = new Edge[m];
                         int[] v2c = new int[n];