Summary

毕竟人类的本质是咕咕咕,
所以先贴了代码有空再详细写.

Code

#pragma gcc optimize(3)
#pragma g++ optimize(3)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

struct strz
{
    int num, val, wei, lqs[1020];
};
struct strf
{
    int val, wei;
};
int n, w, in1, in2, in3, ans, h[10020];
vector<strz> z;
vector<strf> f[10020];
vector<strf> g[10020];

int main()
{
    scanf("%d%d", &n, &w);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &in1, &in2, &in3);
        if (in1)
            f[in1].push_back({in3, in2});
        else
            z.push_back({i, in3, in2, {}});
    }
    for (vector<strz>::iterator i = z.begin(); i != z.end(); i++)
    {
        memset(i->lqs, -1, sizeof(i->lqs));
        i->lqs[0] = 0;
        for (vector<strf>::iterator j = f[i->num].begin(); j != f[i->num].end(); j++)
            for (int k = w - i->wei; k >= j->wei; k--)
                if (i->lqs[k] < i->lqs[k - j->wei] + j->val && i->lqs[k - j->wei] != -1)
                    i->lqs[k] = i->lqs[k - j->wei] + j->val;
        for (int j = 0; j <= w - i->wei; j++)
            if (i->lqs[j] != -1)
                g[i->num].push_back({i->lqs[j] + i->val, j + i->wei});
    }
    for (vector<strz>::iterator i = z.begin(); i != z.end(); i++)
        for (int j = w; j >= 0; j--)
            for (vector<strf>::iterator k = g[i->num].begin(); k != g[i->num].end(); k++)
                if (j >= k->wei)
                    h[j] = max(h[j], h[j - k->wei] + k->val);
    for (int i = 0; i <= w; i++)
        ans = max(ans, h[i]);
    printf("%d", ans);
    return 0;
}