洛谷题单指南-树与图上的动态规划-P1273 有线电视网

原题链接：https://www.luogu.com.cn/problem/P1273

题意解读：给定一棵树，边权是成本，叶子节点的点权是收益，求总收益不为负的情况，从根节点能覆盖的最多叶子数量。

解题思路：

有依赖的背包问题。

1、状态表示

设f[i][j]表示以i为根的子树中选择的叶子节点数是j时的最大收益

设x[i]表示节点i的用户交的费用，y[i]表示到节点i的传输成本

2、状态转移

对于u是叶子节点，

f[u][1] = x[u]，只能选择1个叶子并得到该点权的收益

否则，对于u的所有子树v

从大到小枚举体积，体积最大值是是u下叶子节点数量

再枚举从v中能选的叶子节点数量，从1~min(v的叶子节点数， u的叶子节点数)

f[u][j] = max(f[u][j], f[v][k] + f[u][j - k] - y[v]) //对于非叶子节点，选择之后要减去边权的成本

3、初始化

memset(f, -0x3f, sizeof(f)); // 初始化f数组为负无穷
for(inti=0; i<N; i++) f[i][0] =0; // 0个叶子节点时收益为0
4、结果

i从m到1枚举，使得f[1][i]>=0的第一个i即使最大的叶子数量。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 3005;

vector<int> g[N];
int x[N], y[N]; // x[i]表示节点i的用户交的费用，y[i]表示到节点i的传输成本
int f[N][N]; // f[i][j]表示以i为根的子树中选择的叶子节点数是j时的最大收益
int n, m;

//返回以u为根的子树的叶子节点数
int dfs(int u, int fa)
{
    if(u > n - m)
    {
        f[u][1] = x[u]; // 叶子节点只能选择自己
        return 1;
    }
    int cnt = 0; // 记录子树的叶子节点数
    for(int v : g[u])
    {
        if(v == fa) continue;
        int vcnt = dfs(v, u); // 递归处理子节点
        cnt += vcnt; // 累加子节点的叶子节点数
        for(int j = cnt; j >= 0; j--)
        {
            for(int k = 1; k <= min(j, vcnt); k++)
            {
                f[u][j] = max(f[u][j], f[v][k] + f[u][j - k] - y[v]); 
            }
        }
    }
    return cnt;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n - m; i++)
    {
        int k;
        cin >> k;
        while (k--)
        {
            int j, c;
            cin >> j >> c;
            g[i].push_back(j);
            y[j] = c; // 记录到子节点的传输成本
        }
    }
    for(int i = n - m + 1; i <= n; i++)
    {
        int c;
        cin >> c;
        x[i] = c; // 记录叶子节点的用户交的费用
    }

    memset(f, -0x3f, sizeof(f)); // 初始化f数组为负无穷
    for(int i = 0; i < N; i++) f[i][0] = 0; // 0个叶子节点时收益为0
    dfs(1, 0);
    for(int i = m; i >= 0; i--)
    {
        if(f[1][i] >= 0)
        {
            cout << i; // 输出最大收益不小于0时的最大叶子节点数
            return 0;
        }
    }
    cout << 0;
    return 0;
}