Source code for submission s1146

Spider.java

  1. import java.io.BufferedReader;
  2. import java.io.InputStreamReader;
  3. import java.lang.reflect.Array;
  4. import java.util.Arrays;
  5. import java.util.Comparator;
  6.  
  7. class Line implements Comparable<Line>{
  8. int v1, v2, len, act;
  9.  
  10. Line(int v1, int v2, int len, int act) {
  11. this.v1 = v1;
  12. this.v2 = v2;
  13. this.len = len;
  14. this.act = act;
  15. }
  16.  
  17. @Override
  18. public int compareTo(Line arg0) {
  19. return len - arg0.len;
  20. }
  21. }
  22.  
  23. public class Spider {
  24.  
  25.  
  26. /**
  27. * @param args
  28. */
  29. public static void main(String[] args) throws Exception {
  30.  
  31. String s;
  32. int n, l, v1, v2, len, act;
  33. int[] nodes;
  34. //int[] v1;
  35. //int[] v2;
  36. //int[] len;
  37. //int[] act;
  38. Line[] lines;
  39. int result = 0;
  40.  
  41.  
  42. while (true)
  43. {
  44. s = br.readLine();
  45. if (s == null) break;
  46.  
  47. String[] sp = s.split(" ");
  48. n = Integer.parseInt(sp[0]);
  49. l = Integer.parseInt(sp[1]);
  50.  
  51. nodes = new int[n];
  52. lines = new Line[l];
  53. // v1 = new int[l];
  54. // v2 = new int[l];
  55. // len = new int[l];
  56. // act = new int[l];
  57. for (int i=0; i<n; i++) nodes[i] = i;
  58.  
  59. for (int i=0; i<l; i++) {
  60. s = br.readLine();
  61. sp = s.split(" ");
  62.  
  63. v1 = Integer.parseInt(sp[0]) - 1;
  64. v2 = Integer.parseInt(sp[1]) - 1;
  65. len = Integer.parseInt(sp[2]);
  66. act = 1;
  67. lines[i] = new Line(v1, v2, len, act);
  68. }
  69.  
  70. // spojitost
  71.  
  72. for (int i=0; i<l; i++) {
  73. nodes[ lines[i].v2 ] = nodes[ lines[i].v1 ]; // stejna komponenta
  74. }
  75.  
  76. boolean ok = true;
  77. for (int i=1; i<n; i++) {
  78. if (nodes[i-1] != nodes[i]) {
  79. ok = false;
  80. break;
  81. }
  82. }
  83.  
  84. if (!ok) {
  85. System.out.println("disconnect");
  86. }
  87. else {
  88. for (int i=0; i<n; i++) nodes[i] = 0;
  89. int max = Integer.MIN_VALUE;
  90. int maxi = -1;
  91. for (int i=1; i<l; i++) {
  92. if (lines[i].len > max) {
  93. max = lines[i].len;
  94. maxi = i;
  95. }
  96. }
  97.  
  98. // vyradit max hranu
  99.  
  100. lines[maxi].act = 0;
  101. nodes[ lines[maxi].v2 ] = 1;
  102. nodes[ lines[maxi].v1 ] = 1;
  103.  
  104. // mst
  105. Arrays.sort(lines);
  106.  
  107. for (int i=0; i<lines.length; i++) {
  108. if (lines[i].act == 1) {
  109. // nova minimalni, zkusime pridat do kostry
  110.  
  111. if (!(nodes[ lines[i].v1 ] == 1 && nodes[ lines[i].v2 ] == 1)) {
  112. //System.out.println((lines[i].v1+1) + " -> " + (lines[i].v2+1));
  113. //System.out.println(">" + (nodes[ lines[i].v1]+1));
  114. //System.out.println(">" + (nodes[ lines[i].v2]+1));
  115. result += lines[i].len;
  116. lines[i].act = 0;
  117.  
  118. nodes[ lines[i].v2 ] = 1;
  119. nodes[ lines[i].v1 ] = 1;
  120. }
  121. else {
  122. lines[i].act = 0;
  123. }
  124. }
  125. }
  126.  
  127. System.out.println(result - max);
  128.  
  129. }
  130.  
  131. }
  132. }
  133.  
  134. }
  135.