Source code for submission s1053

Go to diff to previous submission

Fr.java

  1. import java.io.InputStreamReader;
  2. import java.io.BufferedReader;
  3. import java.util.*;
  4.  
  5. public class Fr
  6. {
  7. public static void main(String[] args) throws Exception
  8. {
  9.  
  10. while (br.ready())
  11. {
  12. String s1 = br.readLine();
  13. int n = Integer.parseInt(s1.split(" ")[0]);
  14. node[] nodes = new node[n+1];
  15. boolean[] visited = new boolean[n+1];
  16. for (int i = 1; i<=n; i++)
  17. {
  18. nodes[i] = new node(i);
  19. }
  20. node root = nodes[Integer.parseInt(s1.split(" ")[1])];
  21. for (int i = 0; i < n-1; i++)
  22. {
  23. String[] s = br.readLine().split(" ");
  24. int u = Integer.parseInt(s[0]);
  25. int v = Integer.parseInt(s[1]);
  26. int w = Integer.parseInt(s[2]);
  27. pipe tem = new pipe(w,nodes[u],nodes[v]);
  28. nodes[u].pipes.add(tem);
  29. nodes[v].pipes.add(tem);
  30. }
  31. Stack<node> st = new Stack<node>();
  32. st.push(root);
  33. int curcost = 0;
  34.  
  35. while (!st.empty())
  36. {
  37. node cur = st.pop();
  38. for (pipe p : cur.pipes)
  39. {
  40. if (p.equals(cur.in)) continue;
  41. if (!p.top.equals(cur))
  42. {
  43. node temp = p.top;
  44. p.top = p.bottom;
  45. p.bottom = temp;
  46. }
  47. p.bottom.in = p;
  48. if (!p.bottom.equals(cur))
  49. {
  50. st.push(p.bottom);
  51. }
  52. }
  53. if (cur.pipes.size() == 1&& !cur.equals(root))
  54. {
  55. curcost += cur.in.val;
  56. }
  57. }
  58. st.push(root);
  59.  
  60. while (!st.empty())
  61. {
  62. node cur = st.pop();
  63. visited[cur.n] = true;
  64. boolean allkidsvisted = true;
  65. for (pipe p : cur.pipes)
  66. {
  67. if (p.equals(cur.in)) continue;
  68. allkidsvisted &= visited[p.bottom.n];
  69. }
  70. if (!allkidsvisted)
  71. {
  72. st.push(cur);
  73. for (pipe p : cur.pipes)
  74. {
  75. if (p.equals(cur.in)) continue;
  76. st.push(p.bottom);
  77. }
  78. }
  79. else
  80. {
  81. cur.necvalve = 0;
  82. if (cur.equals(root)) continue;
  83. for (pipe p : cur.pipes)
  84. {
  85. if (p.equals(cur.in)) continue;
  86. cur.necvalve += p.val;
  87. cur.necvalve += p.bottom.necvalve;
  88. }
  89. if (cur.in.val < cur.necvalve)
  90. {
  91. curcost -= cur.necvalve;
  92. curcost += cur.in.val;
  93. }
  94. }
  95. }
  96.  
  97. System.out.println(curcost);
  98.  
  99. }
  100. }
  101. public static class node
  102. {
  103. pipe in;
  104. ArrayList<pipe> pipes;
  105. int n;
  106. int necvalve;
  107. public node(int nn)
  108. {
  109. necvalve = 0;
  110. pipes = new ArrayList<pipe>();
  111. n = nn;
  112. }
  113.  
  114.  
  115. }
  116.  
  117. public static class pipe
  118. {
  119. int val;
  120. node top;
  121. node bottom;
  122. public pipe(int v,node t,node b)
  123. {
  124. val = v;
  125. top = t;
  126. bottom = b;
  127. }
  128. }
  129. }
  130.  

Diff to submission s1032

Fr.java

--- c5.s1032.cteam099.fr.java.0.Fr.java
+++ c5.s1053.cteam099.fr.java.0.Fr.java
@@ -37,8 +37,4 @@
                         {
                                 node cur = st.pop();
-                                if (cur.pipes.size() == 1)
-                                {
-                                        curcost += cur.in.val;
-                                }
                                 for (pipe p : cur.pipes)
                                 {
@@ -56,4 +52,8 @@
                                         }
                                 }
+                                if (cur.pipes.size() == 1&& !cur.equals(root))
+                                {
+                                        curcost += cur.in.val;
+                                }
                         }
                         st.push(root);