绝密航天!启动!
原题链接:116451.三角洲行动Ⅱ(force)2026-05-16 21:44:47
发布于:浙江
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define N 1000
using namespace std;
int n, m, u, v, w;
ll b[105], c[105], f[105][1005];
vector<int>a[105];
void tp(int x) {
for (auto u : a[x]) {
tp(u);
for (int i = N; i >= 1; i--)
for (int j = 1; j <= i; j++)
if (f[x][i - j] < 1e16 and f[u][j] < 1e16)
f[x][i] = min(f[x][i], f[x][i - j] + f[u][j]);
}
for (int i = N; i >= b[x]; i--)
f[x][i] = f[x][i - b[x]] + (f[x][i - b[x]] < 1e16 ? c[x] : 0);
for (int i = 0; i < b[x]; i++)
f[x][i] = 0x3f3f3f3f3f3f3f3f;
}
int main() {
// freopen("force.in", "r", stdin);
// freopen("force.out", "w", stdout);
memset(f, 0x3f, sizeof(f));
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> u >> v >> w;
a[w].pb(i);
b[i] = v, c[i] = u;
f[i][0] = 0;
}
f[0][0] = 0;
tp(0);
for (int i = N; i >= 0; i--) {
if (f[0][i] <= m) {
cout << i;
return 0;
}
}
return 0;
}
全部评论 1
不是我写的

昨天 来自 浙江
0
















有帮助,赞一个