bzoj1722 [USACO06MAR]Milk Team Select
Captain_Paul
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;
}
```