[CHCI 2002 Final Exam #2] 有线电视网

GitHub跳转原题关系图返回列表

将用户数作为背包容量维度，利用树形背包 DP 求解在净收益非负条件下的最大转播用户数。

OJ: luogu

题目 ID: P1273

难度:普及+/提高-

标签:树形 DP背包 DP动态规划

创建: 2026-10-23 23:05

更新: 2026-10-26 14:13

形式化题目

给定一棵包含 $N$ 个节点的有向树，树根为节点 $1$ 。树中的叶子节点共有 $M$ 个，编号为 $N-M+1$ 到 $N$ ，分别代表 $M$ 个用户终端；其余节点为转播中转站。

树上的每条有向边 $(u, v)$ 具有非负权值 $c(u, v)$ ，表示传输信号的成本；每个叶子节点 $i$ 具有非负收益 $P_i$ ，表示用户愿意支付的费用。

若要向一个叶子节点子集 $S$ 提供转播信号，必须在树上激活包含根节点 $1$ 和子集 $S$ 中所有叶子的连通子树。总成本等于该连通子树中所有边的权值之和（重复复用的边仅计费一次），总收入等于 $\sum_{i \in S} P_i$ 。

求在满足总收入不小于总成本（即净收益 $\ge 0$ ）的前提下，子集 $S$ 的最大元素个数 $|S|$ 。

暴力解法

思路

树上的叶子节点总数为 $M$ 。最直接的方法是枚举全部 $2^M$ 种可能的叶子用户子集：

枚举一个二进制掩码 $\text{mask} \in [0, 2^M - 1]$ ，其中第 $i$ 位为 $1$ 表示选取第 $i$ 个叶子节点。
对于每种选法，从每个被选中的叶子节点沿着树边向上攀爬到根节点 $1$ ，标记所有被激活的树边。
统计被激活边的边权总和作为总成本，累加选中叶子的付费作为总收入。
若总收入 $\ge$ 总成本，则用当前选中的叶子个数更新答案的最大值。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-23 23:32
 * update_at: 2026-10-23 23:33
 */
/*
 * 暴力解法说明：
 * 枚举所有用户终端（共有 M 个）的子集，共 2^M 种状态。
 * 对于每个被选中的用户子集：
 * 1. 信号必须从根节点 1 传输到所有被选中的用户，因此需要覆盖连接这些用户到根节点的连通子树。
 * 2. 统计树上被激活的边的权值总和（成本），并计算被选中用户的付费总和（收入）。
 * 3. 若 收入 - 成本 >= 0，则更新最大合法用户数。
 * 时间复杂度为 O(2^M * N)，只适合 M <= 20 的小规模测试数据。
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 105;

struct Edge {
    int to;
    ll w;
};

ll n, m;
vector<Edge> g[MAXN];
ll val[MAXN];
int parent_node[MAXN];
ll parent_edge_cost[MAXN];

void get_parents(int u, int p) {
    for (const auto &e : g[u]) {
        int v = e.to;
        if (v == p) continue;
        parent_node[v] = u;
        parent_edge_cost[v] = e.w;
        get_parents(v, u);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;

    for (int i = 1; i <= n - m; ++i) {
        int k;
        cin >> k;
        for (int j = 0; j < k; ++j) {
            int to;
            ll cost;
            cin >> to >> cost;
            g[i].push_back({to, cost});
        }
    }

    for (int i = n - m + 1; i <= n; ++i) {
        cin >> val[i];
    }

    get_parents(1, 0);

    ll ans = 0;
    // 枚举 2^m 种叶子选择方案
    int total_masks = 1 << m;
    for (int mask = 0; mask < total_masks; ++mask) {
        ll cnt = 0;
        ll income = 0;
        vector<bool> edge_used(n + 1, false);

        for (int i = 0; i < m; ++i) {
            if ((mask >> i) & 1) {
                cnt++;
                int leaf = (n - m + 1) + i;
                income += val[leaf];
                // 向上点亮通往根节点 1 的路径
                int curr = leaf;
                while (curr != 1) {
                    if (edge_used[curr]) break;
                    edge_used[curr] = true;
                    curr = parent_node[curr];
                }
            }
        }

        ll cost = 0;
        for (int i = 2; i <= n; ++i) {
            if (edge_used[i]) {
                cost += parent_edge_cost[i];
            }
        }

        if (income >= cost) {
            ans = max(ans, cnt);
        }
    }

    cout << ans << "\n";
    return 0;
}

复杂度

时间复杂度：共有 $2^M$ 种叶子子集，每次检验需沿树向上标记边，耗时 $O(N)$ 。整体时间复杂度为 $O(2^M \cdot N)$ 。
空间复杂度：存储整棵树及父节点指针需 $O(N)$ 空间。

瓶颈

暴力的时间复杂度随着用户数量 $M$ 呈指数级增长。当 $M \le 20$ 时尚能运行，而本题中 $M \le 3000$ ， $2^M$ 是一个不可逾越的天文数字。

瓶颈在于暴力枚举完全忽视了树形结构的重叠子问题和子树最优子结构：在以任意节点 $u$ 为根的子树中，要给子树内的 $k$ 个叶子提供信号，其内部如何选取使得“子树内叶子收益 - 子树内边权”最大化是一个相对独立的决策问题，与子树外的其他兄弟分支互不干扰。这提示我们应当使用树形动态规划来合并子树状态。

正解

思路

1. 状态维度对调与背包设计

若以“花费或收益”作为 DP 状态的维度，由于边权与费用的累加值域较大且不规则，状态规模难以控制。反之，由于用户数量 $M \le 3000$ ，且最终目标正是最大化用户数，我们可以进行“状态与值对调”：

容量维度：以“选中的叶子用户数量”作为状态维度（范围从 $0$ 到 $M$ ）。
DP 状态值：维护在当前子树内选定该数量用户时所能取得的最大净收益（总收入 - 内部总成本）。

定义 $dp[u][j]$ 表示：在以节点 $u$ 为根的子树中，恰好为 $j$ 个用户终端提供转播信号时，子树内部能获得的最大净收益。

2. 状态初始化

默认所有状态初始化为负无穷 $-\infty$ ，表示该方案不可行（注意净收益本身可能为负数，但必须是合法连通的状态才能参与转移）。
对于任何节点 $u$ ，选 $0$ 个用户时不需要激活子树内任何边，净收益为 $0$ ，即 $dp[u][0] = 0$ 。
对于叶子用户节点 $u$ （ $N-M+1 \le u \le N$ ）：它只有自身 $1$ 个用户，若选 $1$ 个用户则获得收益 $P_u$ ，即 $dp[u][1] = P_u$ ；子树叶子数 $sz[u] = 1$ 。
对于中转站节点 $u$ （ $1 \le u \le N-M$ ）：初始时已合并的叶子数 $sz[u] = 0$ 。

3. 状态转移方程

对于非叶子节点 $u$ ，依次遍历其每条出边 $(u, v)$ ，边权为 $w$ 。先递归求解子节点 $v$ 的所有状态与叶子总数 $sz[v]$ 。

将子树 $v$ 视为一个分组背包物品并入 $u$ 的已有状态中：设 $u$ 在合并 $v$ 之前已累计的叶子数为 $sz[u]$ ，合并后可选的最大叶子数为 $sz[u] + sz[v]$ 。为了避免同一子树产生后效性累加，我们仿照 0/1 背包，从大到小倒序枚举合并后的总用户数 $j \in [sz[u] + sz[v], 0]$ ：再枚举分配给子树 $v$ 的用户数 $k \in [1, \min(sz[v], j)]$ ：

dp[u][j] = \max\Big(dp[u][j],\; dp[u][j - k] + dp[v][k] - w\Big)

说明：

当 $k \ge 1$ 时，子树 $v$ 贡献了 $dp[v][k]$ 的收益，但由于信号需要从 $u$ 传送到 $v$ ，必须支付连接边 $(u, v)$ 的成本 $w$ 。
当 $k = 0$ 时，无需激活边 $(u, v)$ ，贡献为 $0$ ，相当于保留原状态 $dp[u][j]$ ，无需显式减去边权。

更新完所有 $j$ 后，令 $sz[u] \leftarrow sz[u] + sz[v]$ 。

为了看清这个转移到底在做什么, 用一个 $4$ 个节点的小例子把某一次合并逐格算一遍:

节点 $1$ 是根, 它唯一的孩子是节点 $2$ , 边权 $c(1, 2) = 2$ ;
节点 $2$ 有两个孩子, 都是用户终端: 节点 $3$ ( $P_3 = 9$ , $c(2, 3) = 1$ ) 与节点 $4$ ( $P_4 = 5$ , $c(2, 4) = 3$ ).

先在节点 $2$ 上做完全部合并: 合并叶子 $3$ 得到 $dp[2][1] = 9 - 1 = 8$ , 再合并叶子 $4$ 得到 $dp[2][2] = 8 + 5 - 3 = 10$ , 于是儿子状态为 $dp[2] = [\,0,\ 8,\ 10\,]$ (对应 $j = 0, 1, 2$ ). 下表把根节点 $1$ 合并这唯一一个儿子 (边权 $w = 2$ ) 的一轮转移逐格列出: 行是合并后的总用户数 $j$ , 中间三列是“分给儿子 $k$ 个用户”这一来源各自算出的候选值, 最后两列是这一格在合并前与合并后的取值.

总用户数 $j$	$k = 0$ 候选 (不动)	$k = 1$ 候选	$k = 2$ 候选	合并前 $dp[1][j]$	合并后 $dp[1][j]$
$0$	$0$	—	—	$0$	$0$
$1$	$-\infty$	$dp[1][0] + dp[2][1] - 2 = 6$	—	$-\infty$	$6$
$2$	$-\infty$	$dp[1][1] + dp[2][1] - 2 = -\infty$	$dp[1][0] + dp[2][2] - 2 = 8$	$-\infty$	$8$

读表时注意三件事: 第一, $k = 0$ 那一列表示“不往这个儿子的子树里放任何用户”, 状态原样保留, 所以 $j = 0$ 一行的右侧仍等于左侧; 第二, 只要 $k \ge 1$ , 候选值都必须再扣一次边权 $w = 2$ , 因为儿子子树里只要有用户, 边 $(u, v)$ 就被激活, 而这条边无论承载几个用户都只计费一次, 这就是 $-w$ 的来源; 第三, $j = 2$ 行的 $k = 1$ 候选是 $-\infty$ , 原因是倒序枚举让 $j = 2$ 先于 $j = 1$ 被处理, 此刻 $dp[1][1]$ 还停在合并前的 $-\infty$ . 若改成从 $j = 0$ 正序枚举, $dp[1][1]$ 会先被更新成 $6$ , 随后 $j = 2$ 的 $k = 1$ 候选就变成 $6 + 8 - 2 = 12$ , 等于把同一个儿子 $2$ 用了两次, 答案虚高. 核对终点也很直接: $dp[1] = [\,0,\ 6,\ 8\,]$ 中 $dp[1][2] = 8 \ge 0$ , 所以这个小例子最多服务 $2$ 个用户.

下面这张图把 $dp[u][j]$ 的候选值拆成来源, 说明一次合并中每一格的值由哪几部分组成:

flowchart LR
  A["dp[u][j-k]: 父节点合并前的状态"] --> C["相加"]
  B["dp[v][k]: 儿子子树恰好服务 k 个用户"] --> C
  C --> D["减去边权 w: 激活边 u 到 v, 且只计一次"]
  D --> E["dp[u][j] 的一个候选"]
  F["k = 0: 直接保留原来的 dp[u][j]"] --> G["在全部候选中取 max"]
  E --> G

图中上方是 $k \ge 1$ 的一条来源路径: 父节点的旧状态配上儿子的 $k$ 个用户, 再统一扣掉一次边权; 下方是 $k = 0$ 的分支, 它完全不经过减法, 等价于“这个儿子整体不选”. 所有分支最后都汇合到取最大值这一步, 这正是分组背包里“每组只能挑一个 $k$ ”的体现.

4. 提取答案

整棵树的 DFS 遍历结束后，根节点的状态 $dp[1][j]$ 即代表在全局选 $j$ 个用户时的最大净收益。我们从 $j = M$ 递减枚举到 $0$ ：找到第一个满足 $dp[1][j] \ge 0$ 的 $j$ 并输出，即为在不亏本的前提下能服务的最大用户数。由于 $dp[1][0] = 0 \ge 0$ ，一定存在合法解。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-23 23:32
 * update_at: 2026-10-23 23:32
 */
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const ll INF = 0x3f3f3f3f3f3f3f3fLL;
const int MAXN = 3005;

struct Edge {
    int to;
    ll w;
};

ll n, m;
vector<Edge> g[MAXN];
ll val[MAXN];
ll dp[MAXN][MAXN];
ll sz[MAXN]; // 子树中用户终端（叶子）的数量

void dfs(int u) {
    if (u > n - m) {
        // 用户终端
        sz[u] = 1;
        dp[u][0] = 0;
        dp[u][1] = val[u];
        return;
    }

    dp[u][0] = 0;
    sz[u] = 0;

    for (const auto &e : g[u]) {
        int v = e.to;
        ll w = e.w;
        dfs(v);

        // 树上背包合并：从大到小枚举以防止重复计算
        for (ll j = sz[u] + sz[v]; j >= 0; --j) {
            for (ll k = 1; k <= sz[v] && k <= j; ++k) {
                if (dp[u][j - k] != -INF && dp[v][k] != -INF) {
                    dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k] - w);
                }
            }
        }
        sz[u] += sz[v];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    if (!(cin >> n >> m)) return 0;

    for (int i = 1; i <= n - m; ++i) {
        int k;
        cin >> k;
        for (int j = 0; j < k; ++j) {
            int to;
            ll cost;
            cin >> to >> cost;
            g[i].push_back({to, cost});
        }
    }

    for (int i = n - m + 1; i <= n; ++i) {
        cin >> val[i];
    }

    // 初始化 dp 数组为极小值
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= m; ++j) {
            dp[i][j] = -INF;
        }
    }

    dfs(1);

    // 寻找在根节点净收益 >= 0 的最大用户数
    for (ll j = m; j >= 0; --j) {
        if (dp[1][j] >= 0) {
            cout << j << "\n";
            break;
        }
    }

    return 0;
}

复杂度

时间复杂度：在子树合并时，两重循环的枚举上限分别为已合并叶子数 $sz[u]$ 与新子树叶子数 $sz[v]$ 。根据树形背包经典的点对计数分析，树上任意两片叶子 $x$ 和 $y$ 只有在其最近公共祖先（LCA）处的合并循环中被配对遍历一次。因此，整棵树上所有合并循环的内层执行次数之和不超过叶子点对的总数 $\binom{M}{2} = \frac{M(M-1)}{2}$ 。加上树遍历的边开销 $O(N)$ ，总时间复杂度为 $O(N + M^2)$ 。当 $N, M \le 3000$ 时，总操作步数在数百万量级以内，可轻松在毫秒级内跑完。
空间复杂度： DP 数组大小为 $(N + 1) \times (M + 1)$ ，在 $N, M \le 3000$ 时占用约 $3000 \times 3000 \times 8 \text{ Bytes} \approx 72\text{ MB}$ 内存，低于标准 128MB 限制；邻接表与辅助数组占用 $O(N)$ 空间。整体空间复杂度为 $O(N \cdot M)$ 。

总结

本题是经典的树形分组背包动态规划。解题的关键在于：

反向刻画状态：面对边权费用累加难以作为下标的难题，利用目标“最大化用户数”的性质，将用户数量反客为主作为背包容量维度，维护净收益的最大值。
严格子树上下界优化：通过严格按子树内实际叶子数 $sz[u]$ 限制内层循环上界，将朴素 $O(N \cdot M^2)$ 的复杂度成功降阶为点对计数的 $O(N + M^2)$ ，保证了算法的高效性。

P1273 [CHCI 2002 Final Exam #2] 有线电视网

题目描述

某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。

从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。

现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。

写一个程序找出一个方案使得有线电视网在不亏本的情况下使观看转播的用户尽可能多。

输入格式

输入文件的第一行包含两个用空格隔开的整数 $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

text

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

输入输出样例 #3

输入 #3

text

1
2
3
4
59 6
3 2 2 3 2 9 3
2 4 2 5 2
3 6 2 7 2 8 2
4 3 3 3 1 1

输出 #3

text

说明/提示

样例解释

如图所示，共有五个结点。结点 ① 为根结点，即现场直播站，② 为一个中转站，③④⑤ 为用户端，共 $M$ 个，编号从 $N-M+1$ 到 $N$ ，他们为观看比赛分别准备的钱数为 $3$ 、 $4$ 、 $2$ 。

从结点 ① 可以传送信号到结点 ②，费用为 $2$ ；

也可以传送信号到结点 ⑤，费用为 $3$ （第二行数据所示）；

从结点 ② 可以传输信号到结点 ③，费用为 $2$ ；

也可传输信号到结点 ④，费用为 $3$ （第三行数据所示）。

如果要让所有用户（③④⑤）都能看上比赛，则信号传输的总费用为： $2+3+2+3=10$ ，大于用户愿意支付的总费用 $3+4+2=9$ ，有线电视网就亏本了，而只让 ③④ 两个用户看比赛就不亏本了。

[CHCI 2002 Final Exam #2] 有线电视网

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

1. 状态维度对调与背包设计

2. 状态初始化

3. 状态转移方程

4. 提取答案

代码

复杂度

总结