Source code for submission s1055

Go to diff to previous submission

 
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
 
/**
 *
 * @author cteam049
 */
public class Main {
 
    static class Node {
        Map<Integer, Node> sucs = new HashMap<Integer, Main.Node>();
        int value;
        int force;
        int count;
        Node parent;
 
        public Node(int value) {
            this.value = value;
        }
    }
 
    private static boolean appendNode(Node node, int i1, int i2, int i3) {
        if (node.value == i1) {
            Node n = new Node(i2);
            n.force = i3;
            n.parent = node;
            node.sucs.put(i2, n);
 
            return true;
        } else if (node.value == i2) {
            Node n = new Node(i1);
            n.force = i3;
            n.parent = node;
            node.sucs.put(i1, n);
 
            return true;
        } else if (node.sucs.containsKey(i1)) {
            return appendNode(node.sucs.get(i1), i1, i2, i3);
        } else if (node.sucs.containsKey(i2)) {
            return appendNode(node.sucs.get(i2), i1, i2, i3);
        } else {
            for (Node tmp : node.sucs.values()) {
                if (appendNode(tmp, i1, i2, i3)) return true;
            }
        }
        return false;
    }
 
 
    private static void preorder(Node node) {
        System.out.println(node.value);
        for (Node n : node.sucs.values()) {
            preorder(n);
        }
 
    }
 
    private static int solve(Node node) {
        if (node.sucs.isEmpty()) {
            return node.force;
        }
        int sum = 0;
        for (Node n : node.sucs.values()) {
            sum += solve(n);
        }
        if (sum < node.force) {
            return sum;
        }
        return node.force;
    }
 
    private static int solveIterative(Node node) {
        outer:
        while (node.parent != null) {
//            System.out.println("Uzel " + node.value);
            if (node.sucs.isEmpty()) {
                node.count = node.force;
            } else {
                for (Node n : node.sucs.values()) {
//                    System.out.println("Potomek " + n.value);
                    if (n.count == 0) {
                        node = n;
                        continue outer;
                    }
                }
                for (Node n : node.sucs.values()) {
                    node.count += n.count;
                }
                if (node.count > node.force) node.count = node.force;
            }
            node = node.parent;
        }
//        System.out.println("Uzel " + node.value);
        return node.sucs.get(0).count;
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String line = null;
        int n, c;
        while (sc.hasNext()) {
            n = sc.nextInt();
            c = sc.nextInt();
            Node n1 = new Node(c);
            n1.force = Integer.MAX_VALUE;
            n1.parent = null;
 
            for (int i=0 ; i<n-1 ; i++) {
                int i1 = sc.nextInt();
                int i2 = sc.nextInt();
                int i3 = sc.nextInt();
                appendNode(n1, i1, i2, i3);
            }
 
            Node parent = new Node(Integer.MAX_VALUE);
            parent.sucs.put(0, n1);
            parent.force = Integer.MAX_VALUE;
            n1.parent = parent;
            System.out.println(solveIterative(n1));
//            preorder(n1);
//            System.out.println(solve(n1));
        }
    }
 
}
 

Diff to submission s945

--- c5.s945.cteam049.fr.java.0.Main.java
+++ c5.s1055.cteam049.fr.java.0.Main.java
@@ -14,4 +14,6 @@
         int value;
         int force;
+        int count;
+        Node parent;
         
         public Node(int value) {
@@ -24,10 +26,14 @@
             Node n = new Node(i2);
             n.force = i3;
+            n.parent = node;
             node.sucs.put(i2, n);
+            
             return true;
         } else if (node.value == i2) {
             Node n = new Node(i1);
             n.force = i3;
+            n.parent = node;
             node.sucs.put(i1, n);
+            
             return true;
         } else if (node.sucs.containsKey(i1)) {
@@ -66,4 +72,29 @@
     }
     
+    private static int solveIterative(Node node) {
+        outer:
+        while (node.parent != null) {
+//            System.out.println("Uzel " + node.value);
+            if (node.sucs.isEmpty()) {
+                node.count = node.force;
+            } else {
+                for (Node n : node.sucs.values()) {
+//                    System.out.println("Potomek " + n.value);
+                    if (n.count == 0) {
+                        node = n;
+                        continue outer;
+                    }
+                }
+                for (Node n : node.sucs.values()) {
+                    node.count += n.count;
+                }
+                if (node.count > node.force) node.count = node.force;
+            }
+            node = node.parent;
+        }
+//        System.out.println("Uzel " + node.value);
+        return node.sucs.get(0).count;
+    }
+    
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
@@ -75,4 +106,5 @@
             Node n1 = new Node(c);
             n1.force = Integer.MAX_VALUE;
+            n1.parent = null;
             
             for (int i=0 ; i<n-1 ; i++) {
@@ -83,6 +115,11 @@
             }
             
+            Node parent = new Node(Integer.MAX_VALUE);
+            parent.sucs.put(0, n1);
+            parent.force = Integer.MAX_VALUE;
+            n1.parent = parent;
+            System.out.println(solveIterative(n1));
 //            preorder(n1);
-            System.out.println(solve(n1));
+//            System.out.println(solve(n1));
         }
     }