次元传送门：洛谷P1273
思路
一开始想的是普通树形DP 但是好像实现不大好
观摩了一下题解
是树上分组背包
设f[i][j]为以i为根的子树中取j个客户得到的总价值
我们可以以i为根有j组
在每一组中分别又取1个，2个，3个......n个客户
化为背包思想即 j为一共有j组 背包容量为每组的客户数总和 把该节点的每个儿子看成一组 每组中的元素为选一个，选两个...选n个用户
状态转移方程：
f[i][j]=max(f[i][j],f[i][j-k]+f[v][k]-边权);//i为根 j为容量
最后输出f[1][i]>=0的i的最大值 所以反向枚举
代码
#include<iostream>
#include<cstring>
using namespace std;
#define maxn 3010
#define INF 1e9+7
int f[maxn][maxn];
int h[maxn],val[maxn];
int n,m,cnt;
struct Edge
{
int to;
int next;
int w;
}e[maxn*maxn];
void add(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].w=w;
e[cnt].next=h[u];
h[u]=cnt;
}
int dfs(int u)
{
if(u>n-m)//如果是叶子节点
{
f[u][]=val[u];//当前只能取一个客户 就是自己
return ;//返回几个客户
}
int t,sum=;//t为当前组有几个客户 sum为背包容量
for(int i=h[u];i;i=e[i].next)//枚举组
{
int v=e[i].to;
t=dfs(v);
sum+=t;
for(int j=sum;j>=;j--)//枚举容量 倒序
for(int k=;k<=t;k++)//枚举客户数量
{
if(j-k>=) f[u][j]=max(f[u][j],f[u][j-k]+f[v][k]-e[i].w);
//满足背包容量大于客户数量才可以
}
}
return sum;
}
int main()
{
memset(f,~0x3f,sizeof(f));//初始化为一个极小负数 因为可能有负数
cin>>n>>m;
for(int i=;i<=n-m;i++)
{
int size;
cin>>size;
for(int j=;j<=size;j++)
{
int x,y;
cin>>x>>y;
add(i,x,y);
}
}
for(int i=n-m+;i<=n;i++) cin>>val[i];
for(int i=;i<=n;i++) f[i][]=;//初始化 取0个客户的花费为0
dfs();
for(int i=m;i>=;i--)//反向枚举
{
if(f[][i]>=)
{
cout<<i;
return ;
} }
}
https://www.luogu.org/problemnew/show/P1273