P1273 有线电视网
知识点: 分组背包，树形DP
原题面
题意简述
给定一棵根节点为 \(1\)，节点数为 \(n\) 的树，边有边权。
有 \(m\) 个叶节点，叶节点有点权。
选择一棵以 \(1\) 为根的子树，使选择的边权值 \(\le\) 点权值。
最大化选择的叶节点的数量。
\(1\le m。
分析题意
显然可以树形 DP，考虑状态设计。
设状态记录 选择的叶节点的个数时，无法处理边权值 \(\le\) 点权值的限制。
移项有：点权值 \(-\) 边权值 \(\ge 0\)，考虑记录 点权值 \(-\) 边权值的大小。
设 \(f_{i,j}\) 表示，以 \(i\) 为根的子树中选择了 \(j\) 个叶节点时，点权值 \(-\) 边权值最大值。
显然，答案为满足 \(f_{1,j} \ge 0\) 的 \(j\) 的最大值。
有转移方程：
\[f_{u,j} = \max_{k=0}^{size_v} \{f_{u,j-k} +f_{v,k} - w_{u,v}\} \]表示从 \(v\) 的子树中取出 \(k\) 个子节点加入 \(u\) 的子树中，同时计算 \(u,v\) 边权的贡献。
\(size_v\) 为 子树 \(v\) 中叶节点的个数。
可将从 \(v\) 中取出 \(1,2,\dots k\) 个叶节点的贡献，看做 \(k\) 个体积分别为 \(1\sim k\) 的，不同的物品。
\(v\) 只能做一次贡献，是一个显然的分组背包问题。
为防止重复贡献，枚举 \(j\) 时应倒序枚举。
代码实现
//知识点:树形分组背包DP
/*
By:Luckyblock
*/
#include
#include
#include
#include
#define ll long long
const int kMaxn = 3000 + 10;
//=============================================================
struct Edge {
int v, w, ne;
} e[kMaxn << 1];
int n, m, edge_num, head[kMaxn], val[kMaxn], size[kMaxn];
int f[kMaxn][kMaxn];
//=============================================================
inline int read() {
int f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
void GetMax(int &fir, int sec) {
if (sec > fir) fir = sec;
}
void GetMin(int &fir, int sec) {
if (sec < fir) fir = sec;
}
void AddEdge(int u, int v, int w) {
e[++ edge_num].v = v, e[edge_num].w = w;
e[edge_num].ne = head[u], head[u] = edge_num;
}
void Dfs(int u) {
if (u > n - m) {
f[u][1] = val[u]; size[u] = 1;
return ;
}
for (int i = head[u]; i; i = e[i].ne) {
int v = e[i].v, w = e[i].w;
Dfs(v);
size[u] += size[v];
for (int j = size[u]; j >= 0; -- j) {
for (int k = 0; k <= size[v]; ++ k) {
if (j - k < 0) continue ;
GetMax(f[u][j], f[u][j - k] + f[v][k] - w);
}
}
}
}
//=============================================================
int main() {
n = read(), m = read();
for (int u = 1; u <= n - m; ++ u) {
int k = read();
for (int j = 1; j <= k; ++ j) {
int v = read(), w = read();
AddEdge(u, v, w);
}
}
for (int i = n - m + 1; i <= n; ++ i) val[i] = read();
memset(f, 128, sizeof(f)); //利用自然溢出，赋极小值
for (int i = 1; i <= n; ++ i) f[i][0] = 0;
Dfs(1);
for (int i = m; i >= 0; -- i) {
if (f[1][i] >= 0) {
printf("%d\n", i);
break ;
}
}
return 0;
}