HUD 5438 Ponds

Solution Sketch

Key: Use DFS and yank nodes with $total\ degree = 1$

Balancing Act

Solution sketch

在樹上做DP，基本上是挑一個點當作 root 開始 DFS。維護 連同節點$u$在內已經拜訪過的子樹結點總數 和 拔掉節點$u$後最大的子數大小，就可以求出答案。

Optimal Binary Search Tree

Solution sketch

Just like cutting stick!! :)

Coins

Solution sketch

有限背包問題，但是正常做會TLE QQ！（原理請看解說)

Cash Machine

Solution sketch

有限背包問題，需要使用二進制拆解！（請看解說）

Charm Bracelet

Solution sketch

0/1背包問題，需要優化記憶體使用量！

T-shirts Distribution

Solution sketch

Let the source node be $0$, shirt nodes from small to large are $[1, 6]$ respectively, participant nodes are $[7, 7 + n)$, and sink node be $7 + n$.

Internet Bandwidth

Solution sketch

用 Adjacency matrix 存圖後（因為點數很少），之後跑一次 Ford Fulkerson 即可。

Array and Operations

Solution sketch

Gourmet and Banquet

Solution sketch

Construct the flow graph with 1 super source, 10000 time nodes, n dish nodes, and 1 super sink.

Connect super source to all time nodes with cap 1. Connect dish’s time $[a_i, b_i)$ to dish’s node, with cap 1. Connect all dish nodes to the super sink with cap value from binary search.