国庆最后一天的contest

Erengy

Description

“封印大典启动,请出 Nescafe 魂珠!”随着圣主 applepi 一声令下,圣剑护法 rainbow

和魔杖护法 freda 将 Nescafe 魂珠放置于封印台上。封印台是一个树形的结构,魂珠放置的

位置就是根节点(编号为 0)。还有 n 个其它节点(编号 1~n)上放置着封印石,编号为 i

的封印石需要从魂珠上获取 Ei 的能量。能量只能沿着树边从魂珠传向封印石,每条边有一

个能够传递的能量上限 Wi,魂珠的能量是无穷大的。作为封印开始前的准备工作,请你求

出最多能满足多少颗封印石的能量需求?

注意:能量可以经过一个节点,不满足它的需求而传向下一个节点。每条边仅能传递一

次能量。

Input

第一行一个整数 n,表示除根节点之外其它节点的数量。

接下来 n 行,第 $i+1$ 行有三个整数 $Fi$、$Ei$、$Wi$,分别表示 i 号节点的父节点、i 号节点

上封印石的能量需求、连接节点 $i $与$ Fi $的边最多能传递多少能量。

Output

最多能满足多少颗封印石的能量需求

Analysis

​ 这一道题目一眼就可以看出来是一个树上的背包问题,但是毫无疑问,我写着写着,就写错了,最后我也没有写出一个所以然来。而这一道有两种做法,第一种做法是贪心,将能量的需求排一个序,然后每一次选择最少的的那一个来往上修改容量即可,若是不可以,那么久继续往下算就可以了

​ 第二种方法就是树上背包了设$f[i][j]$是$i$子树,消耗$j$的能量,最多有多少个孩子
$$
f[u][i]=max(f[v][k]+f[u][i-k])(v是u的子节点,)
$$

Code

#include<bits/stdc++.h>
using namespace std;

#define maxn 1005
#define maxe 105
#define min(x,y) ( ( (x) < (y) ) ? (x) : (y) )
#define max(x,y) ( ( (x) > (y) ) ? (x) : (y) )

int fa[maxn];
int lim[maxn];
int dmd[maxn];
int id[maxn];
int f[maxn][maxe];
int tot=0,N;
int ans=0;

bool dfs(int u);
bool cmp(int x,int y){return dmd[x]<dmd[y];}

int main(){
ifstream fin("energy.in");
ofstream fout("energy.out");
fin>>N;
for(int i=1;i<=N;i++){
int f,e,w;fin>>f>>e>>w;
dmd[i]=e;fa[i]=f;lim[i]=w;id[i]=i;
}
sort(id+1,id+1+N,cmp);
for(int i=1;i<=N;i++){
if(dfs(id[i]))ans++;
}
fout<<ans;
fin.close();
fout.close();
return 0;
}

bool dfs(int u){
int now=u;
while(now){
if(lim[now]<dmd[u])return false;
now=fa[now];
}
now=u;
while(now){
lim[now]-=dmd[u];
now=fa[now];
}
return true;
}