记录编号 |
444076 |
评测结果 |
AAAAAAAAAA |
题目名称 |
凯伦和超市 |
最终得分 |
100 |
用户昵称 |
Ostmbh |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
2.257 s |
提交时间 |
2017-09-01 22:04:01 |
内存使用 |
383.43 MiB |
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn=5000+10;
long long minn[maxn][maxn][2];
vector<int>A[maxn];
int v[maxn],c[maxn];
int size[maxn];
int n;
inline void dfs(int x){
size[x]=1;
for(int i=0;i<A[x].size();i++){
int u=A[x][i];
dfs(u);
for(int j=size[x];j>=0;j--){
for(int k=0;k<=size[u];k++){
minn[x][j+k][1]=min(minn[x][j+k][1],min(minn[u][k][1],minn[u][k][0])+minn[x][j][1]);
minn[x][j+k][0]=min(minn[x][j+k][0],minn[u][k][0]+minn[x][j][0]);
}
}
size[x]+=size[u];
}
for(int i=n-1;i>=0;i--){
minn[x][i+1][1]=minn[x][i][1]+v[x]-c[x];
minn[x][i+1][0]=min(minn[x][i][0]+v[x],minn[x][i+1][0]);
}
}
int main(){
freopen("market.in","r",stdin);
freopen("market.out","w",stdout);
memset(minn,127/2,sizeof(minn));
long long b;
cin>>n>>b;
for(int i=1;i<=n;i++)
minn[i][0][1]=minn[i][0][0]=0;
int x;
for(int i=1;i<=n;i++){
scanf("%d %d",&v[i],&c[i]);
if(i>=2){
scanf("%d",&x);
A[x].push_back(i);
}
}
dfs(1);
int ans=0;
for(int j=1;j<=n;j++)
if((minn[1][j][1]<=b||minn[1][j][0]<=b)&&j>ans)
ans=j;
printf("%d",ans);
/*for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++){
printf("%d ",minn[i][j][0]);
}
puts("");
}
for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++){
printf("%d ",minn[i][j][1]);
}
puts("");
}*/
return 0;
}