题解 P1273 【有线电视网】
ShuYuMo
2019-10-29 00:46:37
# 写在前面
>树形DP一般就是$f[i][j]$表示以第$i$个结点为根的子树中，$j$个儿子或者价值为$j$，在这道题里面，$j$表示在这个子树中选取$j$个叶子节点。
在AC这道题之前，看过无数题解，这句话是笔者认为写的最精彩的。
# 状态
考虑一钟状态设计方式$f[i][j]$表示在以$i$为根的子树中，选取满足$j$个“叶子”，获得的最大价值。
# 方程
$$f[i][j] = \max_{k = 0}^{k = Size_{exNode}}(f[i][j - k] + f[exNode][k]) - W_x$$
- $f[i][j]$表示在以$i$为根的子树中，选择子树中的$j$个叶子结点获得的最大价值。
- $Size_k$表示子树$k$的大小。
- $exNode$表示$i$的儿子结点。
- $W_x$表示边权。
就是说，选择一部分的$j$（选择满足叶子结点数）分配给$exNode$ $k$个，其余分配给其他结点。这样获得的最大利润。
思考，如果让儿子结点$exNode$为根的子树中，“满足”$k$个叶子结点（用户端）的需求，那么会获得$f[exNode][k]$的利润，再减去信号从$i$传到$exNode$的花费$W_x$，再加上其他结点获得的利润$f[i][j - k]$，就能得到让$exNode$，中的$k$个叶子结点满足的利润。
# 为什么是分组背包
分组背包指在很多组中只能选一种物品，获得的最大利润
回到本题，组就是每一棵子树，物品其实并不是叶子结点，而是叶子节点的满足个数。
比如，在以结点$u$为根的子树中（第$u$组）,有一些物品，这些物品是：
- 满足以结点$u$为根的子树中，$1$个叶子结点的需求。
- 满足以结点$u$为根的子树中，$2$个叶子结点的需求。
- 满足以结点$u$为根的子树中，$3$个叶子结点的需求。
- 满足以结点$u$为根的子树中，$4$个叶子结点的需求。
- 满足以结点$u$为根的子树中，$Size_v$个叶子结点的需求。
每一组的各个元素都是互相矛盾只能选一种的。
这就是分组背包。
对于每一个结点都要进行分组背包。
对于扩展结点时，假如当前结点时$now$， 扩展节点是$exNode$。
应该使用$Size_{exNode}$的每一个可能满足的取值更新$f[now][j]$（取最大值（利润一定要最大啊））
```cpp
int &sum = lef[now];//表示子树大小
for(_R int i = head[now];i;i = edge[i].nxt) {
int exNode = edge[i].node;
int t = dfs(exNode); sum += t;
for(_R int j = lef[now];j >= 0;j--) {
for(_R int k = 0;k <= lef[exNode];k++) {
if(j - k < 0) continue;
dp[now][j] = max(dp[now][j], dp[now][j - k] + dp[exNode][k] - edge[i].w);
}
```
# 关于`for(int j = lef[now];j >= 0;j--)`
倒序枚举的原因同`0-1背包`滚动数组优化后的方法。
防止多次转移，也就是防止在同一组里选重复的元素。
即，
保证每一次$dp[now][j - k]$的取值都是上一个儿子结点更新完答案剩下的，而不是当前美剧道德儿子结点更新答案之后的指。
# 最后的最后
题目没有问能获得的最大利润，而是希望更多的用户能够用上电视，于是只要电视台不亏本，就可以满足。
从打到小枚举$f[1][i]$找一个最大的$i$使$f[1][i] >= 0$
# Codes
```cpp
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define _R register
#define inf 0x7fffffff
using namespace std;
const int _ = 3100;
inline int read()
{
char c = getchar(); int sign = 1; int x = 0;
while(c > '9' || c < '0') { if(c=='-')sign = -1; c = getchar(); }
while(c <= '9' && c >= '0') { x *= 10; x += c - '0'; c = getchar(); }
return x * sign;
}
int n, m;
int nodeVal[_];
int dp[_][_];
int head[_];
struct edge{
int node;
int w;
int nxt;
}edge[_];
int tot = 0;
void add(int u, int v, int w){
edge[++tot].nxt = head[u];
head[u] = tot;
edge[tot].node = v;
edge[tot].w = w;
}
int lef[_];
int dfs(int now)
{
if(now >= n - m + 1) return dp[now][1] = nodeVal[now], lef[now] = 1;
int &sum = lef[now];
for(_R int i = head[now];i;i = edge[i].nxt) {
int exNode = edge[i].node;
int t = dfs(exNode); sum += t;
for(_R int j = lef[now];j >= 0;j--) {
for(_R int k = 0;k <= lef[exNode];k++) {
if(j - k < 0) continue;
dp[now][j] = max(dp[now][j], dp[now][j - k] + dp[exNode][k] - edge[i].w);
}
}
}
return lef[now];
}
int main()
{
n = read(), m = read();
for(_R int i = 1;i <= n - m;i++){
int k = read();
for(_R int j = 1;j <= k;j++){
int A = read();
int C = read();
add(i, A, C);
}
}
for(_R int i = n - m + 1;i <= n;i++){
nodeVal[i] = read();
}
memset(dp, -100, sizeof(dp));
for(_R int i = 1;i <= n;i++) dp[i][0] = 0;
dfs(1);
for(_R int i = m;i >= 0;i--)
if(dp[1][i] >= 0){
return printf("%d\n", i), 0;
}
return 0;
}
```