动态规划之【树形DP】第3课树形DP应用案例实践2有线电视网题目描述某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构这棵树的根结点位于足球比赛的现场树叶为各个用户终端其他中转站为该树的内部节点。从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的一场转播的总费用等于传输信号的费用总和。现在每个用户都准备了一笔费用想观看这场精彩的足球比赛有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。输入格式输入文件的第一行包含两个用空格隔开的整数N NN和M MM其中2 ≤ N ≤ 3000 2 \le N \le 30002≤N≤30001 ≤ M ≤ N − 1 1 \le M \le N-11≤M≤N−1N NN为整个有线电视网的结点总数M MM为用户终端的数量。第一个转播站即树的根结点编号为1 11其他的转播站编号为2 22到N − M N-MN−M用户终端编号为N − M 1 N-M1N−M1到N NN。接下来的N − M N-MN−M行每行表示—个转播站的数据第i 1 i1i1行表示第i ii个转播站的数据其格式如下K A 1 C 1 A 2 C 2 … A k C k K \ \ A_1 \ \ C_1 \ \ A_2 \ \ C_2 \ \ \ldots \ \ A_k \ \ C_kKA1​C1​A2​C2​…Ak​Ck​K KK表示该转播站下接K KK个结点转播站或用户每个结点对应一对整数A AA与C CCA AA表示结点编号C CC表示从当前转播站传输信号到结点A AA的费用。最后一行依次表示所有用户为观看比赛而准备支付的钱数。单次传输成本和用户愿意交的费用均不超过10 1010。输出格式输出文件仅一行包含一个整数表示上述问题所要求的最大用户数。输入输出样例 1输入 15 3 2 2 2 5 3 2 3 2 4 3 3 4 2输出 12输入输出样例 2输入 25 3 2 2 2 5 3 2 3 2 4 3 4 4 2输出 23输入输出样例 3输入 39 6 3 2 2 3 2 9 3 2 4 2 5 2 3 6 2 7 2 8 2 4 3 3 3 1 1输出 35说明/提示样例解释如图所示共有五个结点。结点 ① 为根结点即现场直播站② 为一个中转站③④⑤ 为用户端共M MM个编号从N − M 1 N-M1N−M1到N NN他们为观看比赛分别准备的钱数为3 33、4 44、2 22。从结点 ① 可以传送信号到结点 ②费用为2 22也可以传送信号到结点 ⑤费用为3 33第二行数据所示从结点 ② 可以传输信号到结点 ③费用为2 22也可传输信号到结点 ④费用为3 33第三行数据所示。如果要让所有用户③④⑤都能看上比赛则信号传输的总费用为2 3 2 3 10 232310232310大于用户愿意支付的总费用3 4 2 9 34293429有线电视网就亏本了而只让 ③④ 两个用户看比赛就不亏本了。思路分析问题分析这是一个树形背包 DP问题。树根为信号源结点 1叶子为M个用户内部结点为中转站。每条边有传输费用每个用户愿意支付一定金额。关键点选择若干个用户使总收益用户付费和 − 信号传输费用≥ 0并最大化用户数。信号传输费用计算规则若多个用户共享某条边该边费用只计算一次因为信号一起传输。因此总费用 所有被选用户到根路径的边权并集的总和。转化模型设d p [ u ] [ k ] dp[u][k]dp[u][k]表示在以u uu为根的子树中选择k kk个用户所能获得的最大净收益用户付费 − 传输费用。最终我们需要找到最大的k kk使得d p [ 1 ] [ k ] ≥ 0 dp[1][k] \ge 0dp[1][k]≥0。状态转移对结点u uu的每个子结点v vv边权w ww合并子树v vv时若从v vv中选k kk个用户则边( u , v ) (u,v)(u,v)的费用w ww必须支付一次因为信号要传给这k kk个用户。因此合并后的净收益 当前u uu的旧收益已合并的前面子树 子树v vv的收益 −w ww。转移方程d p [ u ] [ j k ] max ⁡ ( d p [ u ] [ j k ] , d p [ u ] [ j ] d p [ v ] [ k ] − w ) dp[u][jk] \max\big(dp[u][jk],\; dp[u][j] dp[v][k] - w\big)dp[u][jk]max(dp[u][jk],dp[u][j]dp[v][k]−w)初始化非叶子结点d p [ u ] [ 0 ] 0 dp[u][0] 0dp[u][0]0其余为− ∞ -\infty−∞。叶子结点用户d p [ u ] [ 0 ] 0 , d p [ u ] [ 1 ] 用户付费 dp[u][0]0,\; dp[u][1] \text{用户付费}dp[u][0]0,dp[u][1]用户付费。复杂度树形背包合并的总体复杂度为O ( N ⋅ M ) O(N \cdot M)O(N⋅M)N ≤ 3000 N \le 3000N≤3000M ≤ 2999 M \le 2999M≤2999可接受。代码实现#includebits/stdc.husingnamespacestd;constintINF1e9;intn,m;// n:总结点数, m:用户数inthead[3005],to[6005],nxt[6005],w[6005],tot;// 邻接表intdp[3005][3005];// dp[u][k]: 子树u中选k个用户的最大净收益intsz[3005];// 子树u中的用户数intpay[3005];// 用户付费// 添加边 u - v, 权值 cvoidadd(intu,intv,intc){to[tot]v;w[tot]c;nxt[tot]head[u];head[u]tot;}voiddfs(intu){if(un-m){// 叶子结点用户sz[u]1;dp[u][0]0;dp[u][1]pay[u];return;}dp[u][0]0;// 不选任何用户收益0sz[u]0;for(intihead[u];i;inxt[i]){intvto[i],cw[i];dfs(v);// 递归处理子结点// 背包合并倒序枚举保证使用旧值for(intjsz[u];j0;--j){for(intk1;ksz[v];k){if(dp[u][j]!-INFdp[v][k]!-INF){dp[u][jk]max(dp[u][jk],dp[u][j]dp[v][k]-c);}}}sz[u]sz[v];// 更新当前子树用户数}}intmain(){scanf(%d%d,n,m);// 读入内部结点1 ~ n-mfor(inti1;in-m;i){intk;scanf(%d,k);while(k--){inta,c;scanf(%d%d,a,c);add(i,a,c);}}// 读入用户付费编号 n-m1 ~ nfor(intin-m1;in;i){scanf(%d,pay[i]);}// 初始化 dp 为负无穷for(inti1;in;i){for(intj0;jm;j){dp[i][j]-INF;}}dfs(1);// 从根结点开始 DP// 寻找最大 k 使得净收益 ≥ 0intans0;for(intim;i0;--i){if(dp[1][i]0){ansi;break;}}printf(%d\n,ans);return0;}功能分析输入处理第一行读入N和M。接下来N-M行每行第一个整数K表示该中转站的下级结点数之后每对A C表示子结点编号和传输费用。最后一行M个整数依次是每个用户的付费金额用户编号从N-M1到N。树形 DP 过程DFS 递归从根结点 1 开始后序遍历整棵树。叶子结点直接设置dp[u][0]0dp[u][1]pay[u]sz[u]1。内部结点初始化dp[u][0]0sz[u]0。对每个子结点v递归调用后执行背包合并倒序枚举当前已选用户数j从sz[u]到0正序枚举子树的用户数k1 到sz[v]。更新dp[u][jk] max(自身, dp[u][j] dp[v][k] - 边权)。更新sz[u] sz[v]。结果输出从k M向下遍历找到第一个dp[1][k] 0输出k。若没有正收益的方案k0总是可行因为dp[1][0]0完整系列资料请查看专栏《csp信奥赛C动态规划》https://blog.csdn.net/weixin_66461496/category_13096895.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}