1#10#12AC 其余WA

思路是将主，主+附一，主+附二，主加附一加附二放在一组中，然后同P1757 通天之分组背包类似的代码，cnt记组数，代码中有调试

#include<bits/stdc++.h>
using namespace std;
#define int long long
int m,n,cnt=0,sum=0,ans;
int dp[105][40005];
int fjw[1005],fjv[1005];
bool pd[1005];
struct node{
    int w,v,k;
}q[1005];
bool cmp(node q1,node q2){
    return q1.k<q2.k;
}
signed main(){
    cin>>m>>n;
    for (int i=1;i<=n;i++) {
        cin>>q[i].w>>q[i].v>>q[i].k;
        q[i].v*=q[i].w;
        if (q[i].k==0) q[i].k=i;
        else{
            if (pd[q[i].k]==1){
                q[i].w+=q[q[i].k].w;
                q[i].v+=q[q[i].k].v;
                sum++;
                q[n+sum].w=(fjw[q[i].k]+q[i].w);
                q[n+sum].v=(fjv[q[i].k]+q[i].v);
                q[n+sum].k=q[i].k;
            }else{
                fjw[q[i].k]=q[i].w;
                fjv[q[i].k]=q[i].v;
                q[i].w+=q[q[i].k].w;
                q[i].v+=q[q[i].k].v;
                pd[q[i].k]=1;
            }
        }
    }
    n+=sum;
    sort(q+1,q+n+1,cmp);
//  for (int i=1;i<=n;i++) cout<<q[i].w<<" "<<q[i].v<<" "<<q[i].k<<endl;
    for (int i=1;i<=n;i++){
        if (q[i].k!=q[i-1].k) cnt++;
//      cout<<q[i].k<<" "; 
        for (int j=0;j<=m;j++){
            if (j>=q[i].w){
                dp[cnt][j]=max(dp[cnt][j],dp[cnt-1][j-q[i].w]+q[i].v);
            }
            else dp[cnt][j]=max(dp[cnt-1][j],dp[cnt][j]);
        }
    }
    for (int i=1;i<=m;i++)
        ans=max(ans,dp[cnt][i]); 
    cout<<ans;
    return 0;
}