Source code for submission s886

Fr.java

  1. /*
  2.  * To change this template, choose Tools | Templates
  3.  * and open the template in the editor.
  4.  */
  5.  
  6. import java.io.BufferedReader;
  7. import java.io.IOException;
  8. import java.io.InputStreamReader;
  9. import java.util.*;
  10. import java.util.logging.Level;
  11. import java.util.logging.Logger;
  12.  
  13. /**
  14.  *
  15.  * @author cteam039
  16.  */
  17. public class Fr {
  18.  
  19. public static void main(String... args) {
  20. try {
  21.  
  22.  
  23. iteration(scan);
  24. } catch (IOException ex) {
  25. Logger.getLogger(Fr.class.getName()).log(Level.SEVERE, null, ex);
  26. }
  27.  
  28. }
  29.  
  30. public static void iteration(BufferedReader scan) throws IOException {
  31. int points, firstPoint;
  32.  
  33. String line = scan.readLine();
  34. while (line != null && line.split(" ").length == 2) {
  35.  
  36. points = Integer.parseInt(line.split(" ")[0]);
  37. firstPoint = Integer.parseInt(line.split(" ")[1]);
  38. line = scan.readLine();
  39.  
  40. Map<Integer, List<Struc>> map = new HashMap<Integer, List<Fr.Struc>>();
  41.  
  42. for(int i = 0; i < points - 1; i++) {
  43.  
  44. int a = Integer.parseInt(line.split(" ")[0]);
  45. int b = Integer.parseInt(line.split(" ")[1]);
  46. int c = Integer.parseInt(line.split(" ")[2]);
  47.  
  48. if (map.get(a) == null) {
  49. map.put(a, new ArrayList<Fr.Struc>());
  50. }
  51. map.get(a).add(new Struc(b, c));
  52.  
  53. if (map.get(b) == null) {
  54. map.put(b, new ArrayList<Fr.Struc>());
  55. }
  56. map.get(b).add(new Struc(a, c));
  57.  
  58.  
  59. line = scan.readLine();
  60. }
  61. List<Struc> edges = map.get(firstPoint);
  62. int sum = 0;
  63. for (Struc strc : edges) {
  64. int rec = cutOff(strc.line, firstPoint, map);
  65. sum += rec > strc.weight ? strc.weight : rec;
  66. }
  67. System.out.println(sum);
  68.  
  69. }
  70.  
  71. }
  72.  
  73. public static int cutOff(int node, int sourceNode, Map<Integer, List<Struc>> map) {
  74. List<Struc> edges = map.get(node);
  75. int sum = 0;
  76. for (Struc strc : edges) {
  77. if (strc.line != sourceNode) {
  78. int nodeW = cutOff(strc.line, node, map);
  79. // System.out.println("nodeW");
  80. sum += strc.weight > nodeW ? nodeW : strc.weight;
  81. }
  82.  
  83. }
  84. if(sum == 0 ){
  85. return Integer.MAX_VALUE;
  86. }
  87. return sum;
  88. }
  89.  
  90. public static class Struc {
  91.  
  92. int line, weight;
  93.  
  94. public Struc(int line, int weight) {
  95. this.line = line;
  96. this.weight = weight;
  97. }
  98. }
  99. }
  100.