转换成分组背包

#include <iostream>
#include <queue>
#define big long long
using namespace std;
const big mod = 1e9+7;
big n,m,head[1003],cnt,val[1003],in[1003];
struct Edge{
    big next,to;
}edge[604];
struct Node{
    big vol,wor,grp;
}obj[1003];
big g[1003][1003],idx,tot[1003],dp[1003];
queue <big> q;
void add_edge(big u,big v)
{
    edge[++cnt] = {head[u],v};
    head[u] = cnt;
    in[v]++;
}
// 转换成背包？？？
int main()
{
    scanf("%lld %lld",&n,&m);
    for(big i = 1,x,y;i <= n;i++)
    {
        scanf("%lld %lld",&x,&y);
        if(x != 0) add_edge(x,i);
        val[i] = y;
    }
    for(big i = 1;i <= n;i++)
    {
        if(!in[i])
        {
            obj[i] = {1,val[i],++idx};
            q.push(i);
        }
    }
    // 先用拓扑排序转换为分组背包
    while(!q.empty())
    {
        big u = q.front(); q.pop();
        for(big i = head[u]; i;i = edge[i].next)
        {
            big v = edge[i].to;
            if(!--in[v])
            {
                obj[v] = {obj[u].vol+1,obj[u].wor+val[v],obj[u].grp};
                q.push(v);
            }
        }
    }
    for(big i = 1;i <= n;i++)
    {
        big id = obj[i].grp;
        g[id][++tot[id]] = i;
    }
    // 分好组了，每组只能选一个
    for(big i = 1;i <= idx;i++)
    {
        for(big j = m;j >= 0;j--)
        {
            for(big k = 1;k <= tot[i];k++)
            {
                big itm = g[i][k];
                if(j >= obj[itm].vol)
                {
                    dp[j] = max(dp[j],dp[j-obj[itm].vol]+obj[itm].wor);
                }
            }
        }
    }
    printf("%lld",dp[m]);
    return 0;
}