能量獲取

(energy.pas/c/cpp)

題目描述

“封印大典啟動，請出 Nescafe 魂珠！”隨著圣主 applepi 一聲令下，圣劍護法 rainbow和魔杖護法 freda 將 Nescafe 魂珠放置于封印臺上。封印臺是一個樹形的結構，魂珠放置的位置就是根節點（編號為 0）。還有 n 個其它節點（編號 1~n）上放置著封印石，編號為 i的封印石需要從魂珠上獲取 Ei 的能量。能量只能沿著樹邊從魂珠傳向封印石，每條邊有一個能夠傳遞的能量上限 Wi，魂珠的能量是無窮大的。作為封印開始前的準備工作，請你求出最多能滿足多少顆封印石的能量需求？ 注意：能量可以經過一個節點，不滿足它的需求而傳向下一個節點。每條邊僅能傳遞一 次能量。

輸入格式

第一行一個整數 n，表示除根節點之外其它節點的數量。 接下來 n 行，第 i+1 行有三個整數 Fi、Ei、Wi，分別表示 i 號節點的父節點、i 號節點上封印石的能量需求、連接節點 i 與 Fi 的邊最多能傳遞多少能量。

輸出格式

最多能滿足多少顆封印石的能量需求。

樣例輸入

4 0 3 2 0 100 100 1 1 1 2 75 80

樣例輸出

2

數據范圍與約定

對于 100% 的數據，滿足 1<=n<=1000，0<=Fi<=n，0<=Ei,Wi<=100。

考試時想到了用貪心，但是證明了半天仍然不能確定其正確性，結果……送分題只得了20分。血的教訓（霧）告訴我們考試的話就不要分時間證明正確性了，敢寫才有可能得分。

正解思路： 貪心，每次選取能量需求最小的節點，掃描它到根節點的路徑上的邊的容量，看能否滿足，如果能滿足就把它到根節點的路徑上的邊的容量都減去它的需求即可。