【题解】洛谷P1273 有线电视网（树上分组背包）

次元传送门：洛谷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][1]=val[u];//当前只能取一个客户 就是自己 return 1;//返回几个客户 } int t,sum=0;//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>=1;j--)//枚举容量 倒序 for(int k=1;k<=t;k++)//枚举客户数量 { if(j-k>=0) 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=1;i<=n-m;i++) { int size; cin>>size; for(int j=1;j<=size;j++) { int x,y; cin>>x>>y; add(i,x,y); } } for(int i=n-m+1;i<=n;i++) cin>>val[i]; for(int i=1;i<=n;i++) f[i][0]=0;//初始化 取0个客户的花费为0 dfs(1); for(int i=m;i>=1;i--)//反向枚举 { if(f[1][i]>=0) { cout<<i; return 0; } } }

 

https://www.luogu.org/problemnew/show/P1273

转载于:https://www.cnblogs.com/BrokenString/p/9902828.html

相关资源：JAVA上百实例源码以及开源项目