Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class MinimumCuts
- {
- int N;
- Node[] nodes;
- static final int MXVAL = 10000;
- static final int[][] orders = {
- {0, 1, 2},
- {0, 2, 1},
- {1, 0, 2},
- {1, 2, 0},
- {2, 0, 1},
- {2, 1, 0}
- };
- private class Node
- {
- Node left, right;
- int removeCost;
- int[] dp;
- void give(Node n)
- {
- if (left == null)
- left = n;
- else if (right == null)
- right = n;
- else
- throw new RuntimeException();
- }
- int f(int x)
- {
- return Math.min(dp[x], removeCost + x);
- }
- void solve()
- {
- if (left != null) left.solve();
- if (right != null) right.solve();
- dp = new int[MXVAL * 2 + 1];
- for (int x = 0; x < dp.length; x++)
- {
- if (left == null)
- dp[x] = (int) 1e8;
- else if (right == null)
- {
- int x1 = left.f(Math.min(removeCost, x));
- int x2 = Math.min(x, removeCost + left.f(0));
- dp[x] = Math.max(dp[x], x1);
- dp[x] = Math.max(dp[x], x2);
- }
- else
- {
- for (int[] or : orders)
- {
- int v = 0;
- for (int n : or)
- {
- if (n == 0)
- v = left.f(v);
- else if (n == 1)
- v = right.f(v);
- else
- v = Math.min(x, removeCost + v);
- }
- dp[x] = Math.max(dp[x], v);
- }
- }
- }
- }
- }
- public int costPaid(int[] parent, int[] cost)
- {
- this.N = cost.length + 1;
- nodes = new Node[N];
- for (int i = 0; i < N; i++)
- nodes[i] = new Node();
- for (int i = 0; i < N-1; i++)
- {
- nodes[i+1].removeCost = cost[i];
- nodes[parent[i]].give(nodes[i+1]);
- }
- nodes[0].solve();
- return nodes[0].dp[0];
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement