题解：洛谷 P1273 [CHCI 2002 Final Exam #2] 有线电视网

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P1273 [CHCI 2002 Final Exam #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。【输出】输出文件仅一行包含一个整数表示上述问题所要求的最大用户数。【输入样例】5 3 2 2 2 5 3 2 3 2 4 3 3 4 2【输出样例】2【算法标签】#普及plus #树上背包【代码详解】#includebits/stdc.husingnamespacestd;constintN3005;// 定义最大节点数intn,m,k;// n: 总节点数m: 用户数k: 临时变量structNode{intv,c;// 邻接点v和边权c};vectorNodeve[N];// 邻接表存储树intp[N],cnt[N];// p: 用户收益cnt: 子树用户数量intf[N][N];// DP数组f[u][i]: 以u为根的子树选择i个用户的最大收益voiddfs(intu,intfa)// 树形DPu当前节点fa父节点{for(inti0;ive[u].size();i)// 遍历所有子节点{intvve[u][i].v;// 子节点intwve[u][i].c;// 连接u和v的边权if(vfa)// 如果是父节点跳过continue;dfs(v,u);// 递归处理子树cnt[u]cnt[v];// 更新子树用户总数for(intjcnt[u];j1;j--)// 背包容量用户数从大到小枚举{for(intk1;kmin(j,cnt[v]);k)// 从子树v中选择k个用户{// 如果u的j-k个用户或v的k个用户不可行跳过if(f[u][j-k]-0x3f3f3f3f||f[v][k]-0x3f3f3f3f)continue;// 状态转移从子树v中选k个用户加上从u的子树中选j-k个用户减去边权wf[u][j]max(f[u][j],f[u][j-k]f[v][k]-w);}}}}intmain(){cinnm;// 输入总节点数和用户数for(inti1;in-m;i)// 前n-m个节点是转发器{cink;// 输入子节点数量for(intj1;jk;j)// 输入每个子节点{inta,c;cinac;// 子节点编号a边权cve[i].push_back({a,c});// 添加双向边ve[a].push_back({i,c});}}for(intin-m1;in;i)// 后m个节点是用户{cinp[i];// 输入用户收益cnt[i]1;// 用户自身是叶子节点用户数为1}memset(f,-0x3f,sizeof(f));// 初始化DP数组为负无穷表示不可行for(inti1;in-m;i)// 初始化转发器节点f[i][0]0;// 转发器不选用户时收益为0for(intin-m1;in;i)// 初始化用户节点f[i][1]p[i];// 用户节点选自己时收益为p[i]dfs(1,0);// 从根节点1开始树形DPfor(intim;i0;i--)// 从最多用户数开始向下查找{if(f[1][i]0)// 如果根节点选i个用户收益非负{coutiendl;// 输出最大用户数break;}}return0;}【运行结果】5 3 2 2 2 5 3 2 3 2 4 3 3 4 2 2