P1273 有线电视网

题目

P1273 有线电视网

算法标签: 树形$dp$, 递归, 树上背包

思路

根据题意, 树的叶子结点是用户, 中间节点是中转站, 每个用户准备一笔费用, 使得不亏本的情况下使得观看的用户数量最大, 不亏本就是总的收到用户的费用 - 线路上的花费$\ge 0$, 定义状态表示$f[i][j]$表示以$i$为根节点的子树中, 恰好选择了$j$个叶子结点的最大利润, 也就是用户的缴费减去花费

树上背包问题都可以这样进行考虑, 给一定的体积$v$, 能得到的最大价值是多少, 在本题当中就是分配$j$个叶子节点的最大利润

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 3010, M = N << 1;
const int INF = 0x3f3f3f3f;

int n, m;
int head[N], ed[M], ne[M], w[M], idx;
int vals[N];
// f[i][j]表示以i为根节点的子树, 分配j个叶子结点的最大利润
int f[N][N];

void add(int u, int v, int val) {
   
    ed[idx] = v, ne[idx] = head[u], w[idx] = val, head[u] = idx++;
}

int dfs(int u, int fa) {
   
    if (u > n - m) {
   
        f[u][1] = vals[u];
        return 1;
    }

    // g代表u的子节点管辖的叶子结点数量
    int sz = 0, g;
    for (int i = head[u]; ~i; i = ne[i]) {
   
        int v = ed[i];
        if (v == fa) continue;
        g = dfs(v, u);
        sz += g;

        for (int j = sz; j > 0; --j) {
   
            for (int k = 1; k <= min(j, g); ++k) {
   
                f[u][j] = max(f[u][j], f[u][j - k] + f[v][k] - w[i]);
            }
        }
    }

    return sz;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head, -1, sizeof head);
    memset(f, -0x3f, sizeof f);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) f[i][0] = 0;

    for (int i = 1; i <= n - m; ++i) {
   
        int k, v, w;
        cin >> k;
        while (k--) {
   
            cin >> v >> w;
            add(i, v, w);
            add(v, i, w);
        }
    }
    for (int i = n - m + 1; i <= n; ++i) cin >> vals[i];

    dfs(1, -1);

    for (int i = m; i >= 0; --i) {
   
        if (f[1][i] >= 0) {
   
            cout << i << "\n";
            return 0;
        }
    }
    return 0;
}