题解 P1273 【有线电视网】

# 树形dp（分组背包） ###### ~~蒟蒻因为看不懂题解自己写结果一次ac的故事~~ ### 说一下自己的理解 1.明确dp[i][j]含义，表示i节点，选j个用户，能得到的钱的最大值，然后对每个节点做分组背包。 2.怎么看出是分组背包？首先，背包的总容量相当于该点为根节点的子树中所有的用户数量（dp[i][j]的 j 不可能超过它连接的所有用户数）。然后，把该节点的每个儿子看成一组，每组中的元素为选一个，选两个...选n个用户。 3.转移方程 dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[v][k]-这条边的花费) i,j不解释了，v表示枚举到这一组（即i的儿子），k表示枚举到这组中的元素：选k个用户。 4.最后输出dp[1][i]>=0的i的最大值，所以反向枚举。 ###### ~~代码丑~~ ------------ ### 更新一下 #### 说一下分组背包吧qwq #### 分组背包：若干组物品，每组中的物品互相冲突（就是说每组中最多只能选一件物品），求最大价值 #### ~~伪代码如下~~ ``` for(int k=1;k<=总共的组数;k++)//遍历所有的组k for(int j=v;j>=1;j--)//跟01背包类似，倒序枚举背包容量 for(int i=1;i<=组中的元素个数;i++)//遍历这组中所有的元素 ``` ~~仔细看的话和树形dp的代码是一模一样的呢~~ #### 再解释一下这道题的思路 简单来说就是把每个节点看成一个背包啦，它的容量就是以这个节点为根的子树大小，组数就是连接的儿子个数。 每组都有很多选择，选一个，两个，三个用户，把这些选择当做组中的元素就好了，容易看出每组中只能选一个元素，比如你选择了选一个用户，就不可能同时选择选两个用户。 代码： ------------ ```cpp #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int n,m;//n为整个有线电视网的结点总数，m为用户终端的数量 //第一个转播站即树的根结点编号为1，其他的转播站编号为2到n-m，用户终端编号为n-m+1到n int head[3010],k; int val[3010];//用户为观看比赛而准备支付的钱数 int dp[3010][3010];//dp[i][j]表示i节点，选j个用户，能得到的钱的最大值 struct node { int to,next,w; }edge[10000010]; void adde(int u,int v,int w) { edge[++k].to=v; edge[k].next=head[u]; edge[k].w=w; head[u]=k; } int dfs(int u) { if(u>n-m)//u为用户终端 { dp[u][1]=val[u]; return 1; } int sum=0,t; for(int k=head[u];k;k=edge[k].next)//该点连接了几个节点意为有几组，遍历每一组 { int v=edge[k].to; t=dfs(v); sum+=t; //t为该组的元素个数，或是说这个儿子为根的子树大小（这里的大小指子树中用户的个数），sum为该节点最多可以选多少个用户，即背包容量 for(int j=sum;j>0;j--) { for(int i=1;i<=t;i++)//遍历组中的元素，选多少个用户相当于一个元素 { if(j-i>=0) dp[u][j]=max(dp[u][j],dp[u][j-i]+dp[v][i]-edge[k].w); } } } return sum; } int main() { memset(dp,~0x3f,sizeof(dp));//初始化一个极大负值，因为dp可能为负 scanf("%d%d",&n,&m); for(int u=1;u<=n-m;u++) { int size,v,w; scanf("%d",&size); for(int j=1;j<=size;j++) { scanf("%d%d",&v,&w); adde(u,v,w); } } for(int i=n-m+1;i<=n;i++) scanf("%d",&val[i]); for (int i=1;i<=n;i++) dp[i][0]=0;//选0个用户的花费肯定是0啦 dfs(1); for (int i=m;i>=1;i--) if (dp[1][i]>=0) { printf("%d",i); break; } return 0; } ```