记录编号 |
444995 |
评测结果 |
AAAAAAAAAA |
题目名称 |
凯伦和超市 |
最终得分 |
100 |
用户昵称 |
胡嘉兴 |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.780 s |
提交时间 |
2017-09-04 20:33:25 |
内存使用 |
195.01 MiB |
显示代码纯文本
#include <cstdio>
#include <vector>
using namespace std;
#define N 5050
#define INF 99999999
int c[N], d[N], x[N], n, size[N], f[N][N] = {0}, g[N][N] = {0};
vector<int> vec[N];
int min(int a, int b)
{
if(a > b)
{
return b;
}
return a;
}
int max(int a, int b)
{
if(a > b)
{
return a;
}
return b;
}
void dfs(int a)
{
int x = vec[a][0];
size[a] = 1;
for(int i = 1; i <= n; i++)
{
f[a][i] = g[a][i] = INF;
}
f[a][1] = c[a];
g[a][0] = g[a][1] = c[a] - d[a];
for(int i = 1; i <= x; i++)
{
int v = vec[a][i];
dfs(v);
for(int j = size[a]; j >= 0; j--)
{
for(int k = 1; k <= size[v]; k++)
{
f[a][j + k] = min(f[a][j + k], f[a][j] + f[v][k]);
g[a][j + k] = min(g[a][j + k], g[a][j] + min(g[v][k], f[v][k]));
}
}
size[a] += size[v];
}
return;
}
int main()
{
int b, ans = 0;
freopen("market.in", "r", stdin);
freopen("market.out", "w", stdout);
scanf("%d%d", &n, &b);
scanf("%d %d", &c[1], &d[1]);
x[1] = 0;
for(int i = 1; i <= n; i++)
{
vec[i].push_back(0);
}
for(int i = 2; i <= n; i++)
{
scanf("%d%d%d", &c[i], &d[i], &x[i]);
vec[x[i]].push_back(i);
vec[x[i]][0]++;
}
dfs(1);
for(int i = 1; i <= n; i++)
{
if(g[1][i] <= b||f[1][i] <= b)
{
ans = i;
}
}
printf("%d\n", ans);
fclose(stdin);
fclose(stdout);
return 0;
}