能量獲取

(energy.pas/c/cpp)

題目描述

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

輸入格式

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

輸出格式

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

樣例輸入

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

樣例輸出

2

數(shù)據(jù)范圍與約定

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

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

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