P2014 选课

斯德哥尔摩 · 2018-11-05 09:19:15 · 个人记录

P2014 选课

一眼看去——树形背包。

设dp[i][j]表示在以i为根的子树中，必须选i，并且选了j个点的最大权值。

有经验的估计转移方程立马就想好了：

但是多颗子树怎么办？

没事，我们新设立一个树根rt，把所有的原来的树根连到rt的字树上。

然后从rt开始跑树形DP即可。

附代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#define MAXN 310
using namespace std;
int n,m,root,c=1;
int head[MAXN],val[MAXN],deep[MAXN],size[MAXN],dp[MAXN][MAXN];
struct Tree{
    int next,to;
}a[MAXN<<1];
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
inline void add(int x,int y){
    a[c].to=y;a[c].next=head[x];head[x]=c++;
    a[c].to=x;a[c].next=head[y];head[y]=c++;
}
void dfs(int rt){
    size[rt]=1;
    dp[rt][0]=0;dp[rt][1]=val[rt];
    int will;
    for(int i=head[rt];i;i=a[i].next){
        will=a[i].to;
        if(!deep[will]){
            deep[will]=deep[rt]+1;
            dfs(will);
            size[rt]+=size[will];
            for(int j=m+1;j>=1;j--){
                for(int k=1;k<=size[will]&&k<j;k++){
                    dp[rt][j]=max(dp[rt][j],dp[rt][j-k]+dp[will][k]);
                }
            }
        }
    }
}
void work(){
    int x;
    n=read();m=read();
    root=n+1;
    for(int i=1;i<=n;i++){
        x=read();val[i]=read();
        if(x)add(i,x);
        else add(root,i);
    }
    val[root]=0;
    deep[root]=1;
    dfs(root);
    printf("%d\n",dp[root][m+1]);
}
int main(){
    work();
    return 0;
}