能量獲取 Energy

2019-11-11 01:38:36

字體：大中小

供稿：網(wǎng)友

能量獲取

(energy.pas/c/cpp)

題目描述

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

輸入格式

第一行一個整數(shù) n，表示除根節(jié)點(diǎn)之外其它節(jié)點(diǎn)的數(shù)量。接下來 n 行，第 i+1 行有三個整數(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

樣例輸出

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

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

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

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

#include<iostream>#include<cstdio>#include<algorithm>using namespace std;const int MAXN=1000,INF=1001;int n;struct dat{int value,id;}en[MAXN+1];int head[MAXN+1],ecnt;struct node{int next,to,value;} e[MAXN+1];void add(int x,int y,int z){ ecnt++; e[ecnt].to=y; e[ecnt].next=head[x]; head[x]=ecnt; e[ecnt].value=z;}bool cmp(const dat & a,const dat & b){return a.value<b.value;}int ans=0;int main(){ freopen("energy.in","r",stdin); freopen("energy.out","w",stdout); int i; scanf("%d",&n); int F,E,W; for(i=1;i<=n;i++) { scanf("%d%d%d",&F,&E,&W); add(i,F,W); en[i].value=E; en[i].id=i; } sort(en+1,en+n+1,cmp); int minv=INF,tmp; for(i=1;i<=n;i++) { minv=INF; for(tmp=en[i].id;tmp;tmp=e[head[tmp]].to) if(e[head[tmp]].value<minv) minv=e[head[tmp]].value; if(minv>=en[i].value) { ans++; for(tmp=en[i].id;tmp;tmp=e[head[tmp]].to) e[head[tmp]].value-=en[i].value; } }