【LuoGU 1273】有线电视网——树上分组背包问题
有线电视网
题目描述
某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。
从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。
现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。
写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。
输入格式
输入文件的第一行包含两个用空格隔开的整数 \(N\) 和 \(M\)，其中 \(2 \le N \le 3000\)，\(1 \le M \le N-1\)，\(N\) 为整个有线电视网的结点总数，\(M\) 为用户终端的数量。
第一个转播站即树的根结点编号为 \(1\)，其他的转播站编号为 \(2\) 到 \(N-M\)，用户终端编号为 \(N-M+1\) 到 \(N\)。
接下来的 \(N-M\) 行每行表示—个转播站的数据，第 \(i+1\) 行表示第 \(i\) 个转播站的数据，其格式如下：
\(K \ \ A_1 \ \ C_1 \ \ A_2 \ \ C_2 \ \ \ldots \ \ A_k \ \ C_k\)
\(K\) 表示该转播站下接 \(K\) 个结点（转播站或用户），每个结点对应一对整数 \(A\) 与 \(C\) ，\(A\) 表示结点编号，\(C\) 表示从当前转播站传输信号到结点 \(A\) 的费用。最后一行依次表示所有用户为观看比赛而准备支付的钱数。单次传输成本和用户愿意交的费用均不超过 10。
输出格式
输出文件仅一行，包含一个整数，表示上述问题所要求的最大用户数。
样例 #1
样例输入 #1
5 3
2 2 2 5 3
2 3 2 4 3
3 4 2
样例输出 #1
2
提示
样例解释
如图所示，共有五个结点。结点 ① 为根结点，即现场直播站，② 为一个中转站，③④⑤ 为用户端，共 \(M\) 个，编号从 \(N-M+1\) 到 \(N\)，他们为观看比赛分别准备的钱数为 \(3\)、\(4\)、\(2\)。
从结点 ① 可以传送信号到结点 ②，费用为 \(2\)；
也可以传送信号到结点 ⑤，费用为 \(3\)（第二行数据所示）；
从结点 ② 可以传输信号到结点 ③，费用为\(2\)；
也可传输信号到结点 ④，费用为 \(3\)（第三行数据所示）。
如果要让所有用户（③④⑤）都能看上比赛，则信号传输的总费用为：\(2+3+2+3=10\)，大于用户愿意支付的总费用 \(3+4+2=9\)，有线电视网就亏本了，而只让 ③④ 两个用户看比赛就不亏本了。
解法
注意到本题的特征：从若干个物品中选出一些来满足某一个限制条件，符合背包问题的特征，因此我们可以从背包问题出发思考。
题目中要选择的目标是树的叶子节点，由于叶节点被子树分成了若干个组，因此这个问题就是一个分组背包问题：
分组背包问题模板(滚动数组优化版本)
for(int i = 1; i <= n; i ++ ){ //组数
for(int j = V; j >= 0; j -- ){ //背包容量
for(int k = 0; k <= sz[i]; k ++ ){ //枚举每一组中的物品
int vik = v[i][k], wik = w[i][k];
if(j >= vik) f[j] = std::max(f[j], f[j - vik] + wik);
}
}
}
设\(f[u][i][j]\)表示结点\(u\)的前\(i\)个儿子中选择\(j\)个结点的最大利润。我们考虑最后一个分界点：如果不取第\(i\)个结点，则状态转移为$$f[u][i][j] = f[u][i - 1][j]$$如果取第\(i\)个结点，记为\(v\)，那么状态转移方程为$$f[u][i][j] = f[u][i - 1][j - k] + f[v][sz[v]][k] - w_{u, v}$$其中\(sz[v]\)表示\(v\)的子树大小，\(k\)表示从\(v\)的子树中选择的节点个数，\(w_{u, v}\)是\(u,v\)之间的花费.所以最终的状态转移方程为$$f[u][i][j] = max_{v \in son[u]}(f[u][i-1][j], f[u][i-1][j-k]+f[v][sz[v]][k] - w_{u,v})$$
显然根据\(0/1\)背包的思想我们可以对上式进行空间优化，只需要在枚举选择的节点个数时倒序枚举即可。优化后的状态转移方程为$$f[u][j] = max_{v \in son[u]}(f[u][j], f[u][j - k] + f[v][k] - w_{u, v})$$
注意本题最终问的问题，是要在不亏本的情况下能够观看转播的最多用户数，也就是满足\(f[1][j] \geq 0\)的最大的\(j\)，因此在做完后需要从大到小枚举\(j\)来找到答案。
#include<bits/stdc++.h>
const int N = 3010;
const int inf = 0xcfcfcfcf;
int n, m;
std::vector<std::vector<std::pair<int, int>>> g(N);
std::vector<std::vector<int>> f(N, std::vector<int>(N, inf));
int sz[N], money[N];
void dfs(int u) {
if(money[u]) {
f[u][1] = money[u];
sz[u] = 1;
return;
}
for(auto edge: g[u]) {
int v = edge.first, w = edge.second;
dfs(v);
sz[u] += sz[v];
for(int j = m; j >= 1; j -- ) {
for(int k = 0; k <= std::min(j, sz[v]); k ++ ) {
f[u][j] = std::max(f[u][j], f[u][j - k] + f[v][k] - w);
}
}
}
}
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n >> m;
for(int i = 1; i <= n - m; i ++ ) {
int k;
std::cin >> k;
for(int j = 0; j < k; j ++ ) {
int a, c;
std::cin >> a >> c;
g[i].push_back({a, c});
}
}
for(int i = n - m + 1; i <= n; i ++ ) {
std::cin >> money[i];
}
for(int i = 1; i <= n; i ++ ) f[i][0] = 0;
dfs(1);
int ans = 0;
for(int i = m; i >= 1; i -- ) {
if(f[1][i] >= 0) {
ans = i;
break;
}
}
std::cout << ans;
return 0;
}