P2064 - 「Poetize10」能量获取

P2064 - 「Poetize10」能量获取
From lydliyudong Normal (OI)
总时限：10s 内存限制：128MB 代码长度限制：64KB
描述 Description

“封印大典启动，请出Nescafe魂珠！”随着圣主applepi一声令下，圣剑易做图rainbow和魔杖易做图freda将Nescafe魂珠放置于封印台上。封印台是一个树形的结构，魂珠放置的位置就是根节点（编号为0）。还有n个其它节点（编号1~n）上放置着封印石，编号为i的封印石需要从魂珠上获取Ei的能量。能量只能沿着树边从魂珠传向封印石，每条边有一个能够传递的能量上限Wi，魂珠的能量是无穷大的。作为封印开始前的准备工作，请你求出最多能满足多少颗封印石的能量需求？
注意：能量可以经过一个节点，不满足它的需求而传向下一个节点。每条边仅能传递一次能量。
输入格式 InputFormat

第一行一个整数n，表示除根节点之外其它节点的数量。
接下来n行，第i+1行有三个整数Fi、Ei、Wi，分别表示i号节点的父节点、i号节点上封印石的能量需求、连接节点i与Fi的边最多能传递多少能量。
样例输入 SampleInput [复制数据]

4
0 3 2
0 100 100
1 1 1
2 75 80
样例输出 SampleOutput [复制数据]

2
数据范围和注释 Hint

对于 100% 的数据，满足1<=n<=1000，0<=Fi<=n，0<=Ei,Wi<=100。
时间限制 TimeLimitation

各个测试点1s

此题贪心贪最小的点，易证必最优解

[delphi]
Program energy;
const
   maxn=1000;
var
   n,i,j,ans:longint;
   f,e,w,num,hpos:array[0..maxn] of longint;
procedure swap(var a,b:longint);
var
   t:longint;
begin
   t:=a;a:=b;b:=t;
end;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
procedure qsort(l,r:longint);
var
   i,j,m,p:longint;
begin
   i:=l;
   j:=r;
   m:=e[(l+r) div 2];
   repeat
      while (e[i]<m) do inc(i);
      while (e[j]>m) do dec(j);
      if (i<=j) then
      begin
         swap(e[i],e[j]);
         swap(f[i],f[j]);
         swap(w[i],w[j]);
         swap(num[i],num[j]);
         inc(i);dec(j);
      end;
   until i>j;
   if (l<j) then qsort(l,j);
   if (i<r) then qsort(i,r);

end;

procedure pour(x:longint);
var
   noww,i,j:longint;
begin
   noww:=maxlongint;
   i:=x;
   while (i<>0) do
   begin
      noww:=min(noww,w[i]);
      i:=hpos[f[i]];
   end;

   if (noww<e[x]) then exit;

   inc(ans);
   i:=x;
   while (i<>0) do
   begin
      dec(w[i],e[x]);
      i:=hpos[f[i]];
   end;
end;
begin
   readln(n);
   for i:=1 to n do
   begin
      read(f[i],e[i],w[i]);
      num[i]:=i;
   end;
   qsort(1,n);
   hpos[0]:=0;
   for i:=1 to n do hpos[num[i]]:=i;

//   for i:=1 to n do write(f[i],' ',e[i],' ',w[i]);

   ans:=0;
   for i:=1 to n do pour(i);
   writeln(ans);

end.

补充：综合编程 , 其他综合 ,