bzoj1722 [USACO06MAR]Milk Team Select

2018-10-08 19:16:12


题意:给一棵带点权树,选出一个点权和 $>=m$ 的点集,最大化其中相邻的点的数量


定义 $f[i][j][0/1]$ 为:以 $i$ 为根的子树中,选择 $j$ 对相邻的点,不选/选根节点时最大的点权和

那么有转移方程:

$f[i][j][0]=max(f[i][j][0],f[i][j-t][0]+max(f[v][t][0],f[v][t][1])),(t<=j)$

$f[i][j][1]=max(f[i][j][1],f[i][j-t][1]+f[v][t][0]),(t<=j)$

$f[i][j][1]=max(f[i][j][1],f[i][j-t-1][1]+f[v][t][1]),(t<j)$

其中初始值 $f[i][0][0/1]=0,f[i][j][1]=w[i]$ ,其余设为 $-inf$

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=505;
struct node
{
    int to,nxt;
}edge[N<<1];
int n,m,num,head[N],w[N],f[N][N][2],tot[N],ans=-1;
inline void add_edge(int from,int to)
{
    edge[++num]=(node){to,head[from]};
    head[from]=num;
}
void dfs(int k)
{
    tot[k]=1;
    for (int i=head[k];i;i=edge[i].nxt)
    {
        int v=edge[i].to; dfs(v); tot[k]+=tot[v];
        for (int j=tot[k]-1;~j;j--)
        {
            for (int t=0;t<tot[v]&&t<=j;t++) 
              f[k][j][0]=max(f[k][j][0],f[k][j-t][0]+max(f[v][t][0],f[v][t][1]));
            if (!k) continue;
            for (int t=0;t<tot[v]&&t<=j;t++)
              f[k][j][1]=max(f[k][j][1],f[k][j-t][1]+f[v][t][0]);
            for (int t=0;t<tot[v]&&t<j;t++)
              f[k][j][1]=max(f[k][j][1],f[k][j-t-1][1]+f[v][t][1]);
        }
    }
    for (int i=0;i<tot[k];i++) f[k][i][1]+=w[k];
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1,x;i<=n;i++)
    {
        scanf("%d%d",&w[i],&x);
        add_edge(x,i);
    }
    memset(f,-0x3f,sizeof(f));
    for (int i=0;i<=n;i++) f[i][0][0]=f[i][0][1]=0;
    dfs(0);
    for (int i=tot[0];~i;i--) if (f[0][i][0]>=m) {ans=i; break;}
    printf("%d\n",ans);
    return 0;
}