题解：洛谷 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≤3000，1 ≤ M ≤ N − 1 1 \le M \le N-11≤M≤N−1，N NN为整个有线电视网的结点总数，M MM为用户终端的数量。

第一个转播站即树的根结点编号为1 11，其他的转播站编号为2 22到N − M N-MN−M，用户终端编号为N − M + 1 N-M+1N−M+1到N NN。

接下来的N − M N-MN−M行每行表示—个转播站的数据，第i + 1 i+1i+1行表示第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 CC，A AA表示结点编号，C CC表示从当前转播站传输信号到结点A AA的费用。

最后一行依次表示所有用户为观看比赛而准备支付的钱数。单次传输成本和用户愿意交的费用均不超过10 1010。

【输出】

输出文件仅一行，包含一个整数，表示上述问题所要求的最大用户数。

【输入样例】

5 3 2 2 2 5 3 2 3 2 4 3 3 4 2

【输出样例】

2

【算法标签】

#普及plus #树上背包

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;constintN=3005;// 定义最大节点数intn,m,k;// n: 总节点数，m: 用户数，k: 临时变量structNode{intv,c;// 邻接点v和边权c};vector<Node>ve[N];// 邻接表存储树intp[N],cnt[N];// p: 用户收益，cnt: 子树用户数量intf[N][N];// DP数组，f[u][i]: 以u为根的子树选择i个用户的最大收益voiddfs(intu,intfa)// 树形DP，u当前节点，fa父节点{for(inti=0;i<ve[u].size();i++)// 遍历所有子节点{intv=ve[u][i].v;// 子节点intw=ve[u][i].c;// 连接u和v的边权if(v==fa)// 如果是父节点，跳过continue;dfs(v,u);// 递归处理子树cnt[u]+=cnt[v];// 更新子树用户总数for(intj=cnt[u];j>=1;j--)// 背包容量（用户数）从大到小枚举{for(intk=1;k<=min(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(){cin>>n>>m;// 输入总节点数和用户数for(inti=1;i<=n-m;i++)// 前n-m个节点是转发器{cin>>k;// 输入子节点数量for(intj=1;j<=k;j++)// 输入每个子节点{inta,c;cin>>a>>c;// 子节点编号a，边权cve[i].push_back({a,c});// 添加双向边ve[a].push_back({i,c});}}for(inti=n-m+1;i<=n;i++)// 后m个节点是用户{cin>>p[i];// 输入用户收益cnt[i]=1;// 用户自身是叶子节点，用户数为1}memset(f,-0x3f,sizeof(f));// 初始化DP数组为负无穷，表示不可行for(inti=1;i<=n-m;i++)// 初始化转发器节点f[i][0]=0;// 转发器不选用户时收益为0for(inti=n-m+1;i<=n;i++)// 初始化用户节点f[i][1]=p[i];// 用户节点选自己时收益为p[i]dfs(1,0);// 从根节点1开始树形DPfor(inti=m;i>=0;i--)// 从最多用户数开始向下查找{if(f[1][i]>=0)// 如果根节点选i个用户收益非负{cout<<i<<endl;// 输出最大用户数break;}}return0;}

【运行结果】

5 3 2 2 2 5 3 2 3 2 4 3 3 4 2 2