比赛 |
树立信心的模拟赛 |
评测结果 |
WWWWWWWWWW |
题目名称 |
凯伦和超市 |
最终得分 |
0 |
用户昵称 |
Shirry |
运行时间 |
1.016 s |
代码语言 |
C++ |
内存使用 |
191.97 MiB |
提交时间 |
2017-09-01 21:59:25 |
显示代码纯文本
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=5010;
int n,m,b[maxn],c[maxn],d[maxn],x[maxn],f[2][maxn][maxn];
int son[maxn];
vector<int>edge[maxn];
int dfs(int x,int y){
son[x]=1;
f[1][x][0]=0;
f[1][x][1]=c[x];//不用优惠券
f[0][x][1]=c[x]-b[x];//用优惠券
for(int k=0;k<(int)edge[x].size();k++){
int p=edge[x][k];
if(p==y)continue;
dfs(p,x);
for(int i=son[x];i>=0;i--){
for(int j=son[p];j>=0;j--){
f[0][x][i+j]=min(f[0][x][i+j],f[0][x][i]+min(f[1][p][j],f[0][p][j]));
f[1][x][i+j]=min(f[1][x][i+j],f[1][x][i]+f[1][p][j]);
}
}
son[x]+=son[p];
}
}
int main(){
freopen("market.in","r",stdin);
freopen("market.out","w",stdout);
scanf("%d%d",&n,&b);
memset(son,0,sizeof(son));
memset(f,0x3f3f3f,sizeof(f));
int t;
for(int i=1;i<=n;i++){
scanf("%d%d",&c[i],&b[i]);
if(i>=2)scanf("%d",&t),edge[t].push_back(i);
}
dfs(1,-1);
for(int i=n;i>=0;i--){
long long minn=min(f[1][1][i],f[0][1][i]);
if(minn<=m){
printf("%d\n",i);
break;
}
}
return 0;
}