P1273 有线电视网 · 习题解析｜信息学奥赛算法练功房

0题目原文（本地存了一份）

为什么要在这儿抄一份题面

原题在洛谷上（页头有链接）。别人的网站不归我们管，打不开、改版、题号调整都可能发生。所以每个解析页都把题面转录一份存在本地，跟着仓库一起进版本库（原题那张样例解释图也存了）。

转录自洛谷 P1273，日期见页头。两边不一致时信原站。

题目描述

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

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

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

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

输入格式

输入文件的第一行包含两个用空格隔开的整数 N 和 M，其中 2 ≤ N ≤ 3000，1 ≤ M ≤ N−1， N 为整个有线电视网的结点总数，M 为用户终端的数量。

第一个转播站即树的根结点编号为 1，其他的转播站编号为 2 到 N−M， 用户终端编号为 N−M+1 到 N。

接下来的 N−M 行每行表示一个转播站的数据，第 i+1 行表示第 i 个转播站的数据，其格式如下：

K A₁ C₁ A₂ C₂ … A_k C_k

K 表示该转播站下接 K 个结点（转播站或用户），每个结点对应一对整数 A 与 C， A 表示结点编号，C 表示从当前转播站传输信号到结点 A 的费用。

最后一行依次表示所有用户为观看比赛而准备支付的钱数。 单次传输成本和用户愿意交的费用均不超过 10。

输出格式

输出文件仅一行，包含一个整数，表示上述问题所要求的最大用户数。

说明/提示

样例解释

P1273 样例解释：五个结点的转播网

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

从结点 ① 可以传送信号到结点 ②，费用为 2；也可以传送信号到结点 ⑤，费用为 3（第二行数据所示）；从结点 ② 可以传输信号到结点 ③，费用为 2；也可传输信号到结点 ④，费用为 3（第三行数据所示）。

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

输入输出样例

输入

输出

就是上面那张图。让 ③④ 看 ⇒ 收 3+4 = 7，铺 ①—②（2）、②—③（2）、②—④（3）共 7 ⇒ 不亏 ⇒ 2。

⚠ 注意 ①—② 那条线：③ 和 ④ 共用它，只付一次钱。 成本是共享的 —— 这一句就是第 ① 步那个贪心栽的地方。

1★ 第一版：按「自己出的钱减去自己那条路的成本」排个序

p1273Greedy.cpp✗ 第一版：按净赚排序，能加就加

// ✗ P1273 第一版：按「自己出的钱 − 自己那条路的成本」从大到小，能加就加
//
// ★ 它错在**成本是共享的**：两个用户共用的那一段线只付一次钱，
//   而这个排序是按「每个人单独拉一条线」算的。
// ⇒ 它每一步都真的验了一遍「加进来还亏不亏」，所以给出的是一个**合法方案**
//   ⇒ 它的用户数**恒 ≤ 正解**。

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

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> fa(n + 1, 0), cost(n + 1, 0), pay(n + 1, 0);
    for (int i = 1; i <= n - m; i++) {
        int k;
        cin >> k;
        for (int t = 0; t < k; t++) { int a, c; cin >> a >> c; fa[a] = i; cost[a] = c; }
    }
    for (int i = n - m + 1; i <= n; i++) cin >> pay[i];

    auto pathCost = [&](int u) { int s = 0; while (u != 1) { s += cost[u]; u = fa[u]; } return s; };

    vector<int> ord;
    for (int u = n - m + 1; u <= n; u++) ord.push_back(u);
    sort(ord.begin(), ord.end(), [&](int a, int b) {
        return pay[a] - pathCost(a) > pay[b] - pathCost(b);
    });

    vector<char> on(n + 1, 0);
    long long income = 0, spend = 0;
    int cnt = 0;
    for (int u : ord) {
        vector<int> added;
        int x = u, extra = 0;
        while (x != 1 && !on[x]) { added.push_back(x); extra += cost[x]; x = fa[x]; }
        if (income + pay[u] - (spend + extra) < 0) {            // 加进来会亏，就不加
            continue;
        }
        for (int y : added) on[y] = 1;
        income += pay[u];
        spend += extra;
        cnt++;
    }
    cout << cnt << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★ 它错在「成本是共享的」，而它排序时是按「每人单拉一条线」算的

它每加一个用户都真的验了一遍「加进来还亏不亏」⇒ 它给出的是一个合法方案 ⇒ 它的用户数恒 ≤ 正解。


它 ≤ 正解	★ 300 / 300
300 轮被抓	39
错的时候平均少服务	3.03 个用户

★ 官方样例就挡住了它：样例①上它一个用户都服务不了（0 vs 正解 2）—— 因为它按「单独拉线」算，③ 和 ④ 各自都是亏的，可合起来就不亏。

2★★ 关键的一步：状态里存的是余额，而「几个用户」当容量

★ f[u][j] = 在 u 的子树里恰好服务 j 个用户时，最大的「收入 − 成本」

题目问的是「不亏本的前提下最多几个用户」。两个量，一个当目标、一个当容量 —— 选错了就做不下去：

把「用户数」当目标、成本当限制 ⇒ 成本的上限是多少？没有上限，因为收入也在变；
★ 把「用户数」当容量、余额当价值 ⇒ 每个 j 算出一个最大余额，最后从大到小找第一个 f[1][j] ≥ 0 就是答案。

转移就是第 25 章的分组背包：每个儿子是一组，在它那边服务 k 个用户，代价是那条边的钱：

    f[u][j] = max over k ≥ 1:  f[u][j-k] + f[v][k] - c(u, v)

⚠ 初值必须是 −∞（只有 f[u][0] = 0）——「恰好 j 个」这句话全靠它。

p1273.cpp★ 这一版就能 AC

// P1273 有线电视网 —— 正解：树形背包（分组背包版），O(n²)
//
//   f[u][j] = 在 u 的子树里**恰好**让 j 个用户看上比赛时，能拿到的最大「收入 − 成本」
//
// ★ 状态里存的是**余额**，不是成本 —— 因为题目问的是「不亏本的前提下最多几个用户」，
//   而「几个用户」这件事必须当**容量**来枚举。
// 答案 = 最大的那个 j，使 f[1][j] ≥ 0。
//
// ⚠ 初值必须是 −∞（只有 f[u][0] = 0）—— 「恰好 j 个」这句话全靠它。
//    写成 0 的话，「凑不出 j 个用户」和「凑出来不赚不亏」就分不开了（见 p1273Zero.cpp）。

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

const int MAXN = 3005;
const int NEG = -1e9;
int n, m, pay[MAXN], sz[MAXN];
vector<pair<int, int>> son[MAXN];        // (儿子, 这条边的费用)
vector<vector<int>> f;

void dfs(int u) {
    if (u > n - m) {                     // 用户终端：一片叶子
        sz[u] = 1;
        f[u][0] = 0;
        f[u][1] = pay[u];
        return;
    }
    sz[u] = 0;
    f[u][0] = 0;
    for (auto& pr : son[u]) {
        int v = pr.first, c = pr.second;
        dfs(v);
        sz[u] += sz[v];
        for (int j = min(sz[u], m); j >= 1; j--)          // ← 倒序
            for (int k = 1; k <= min(sz[v], j); k++)
                if (f[u][j - k] > NEG / 2 && f[v][k] > NEG / 2)
                    f[u][j] = max(f[u][j], f[u][j - k] + f[v][k] - c);
    }
}

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 t = 0; t < k; t++) {
            int a, c;
            cin >> a >> c;
            son[i].push_back({a, c});
        }
    }
    for (int i = n - m + 1; i <= n; i++) cin >> pay[i];

    f.assign(n + 1, vector<int>(m + 1, NEG));
    dfs(1);

    int ans = 0;
    for (int j = m; j >= 0; j--) if (f[1][j] >= 0) { ans = j; break; }
    cout << ans << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

3★★★ 第二个错法：初值写成 0 —— 本章第三个「恒输出一个常量」

p1273Zero.cpp✗ f 的初值写成了 0

// ✗ P1273：f 的初值写成了 0，而不是 −∞
//
// ★ 它算了什么：`f[u][j]` 原本的意思是「**恰好** j 个用户」，
//    而这句话完全靠「凑不出来的格子是 −∞」撑着。
//    初值一写成 0，「凑不出 j 个用户」和「凑出来不赚不亏」就成了同一件事
//    ⇒ 每一格都 ≥ 0 ⇒ 它**恒输出 M**（把所有用户都算成看得上）。
//
// ⚠ 这是本章第三个「恒输出一个常量」的 bug（另外两个在 [P1352] 和 [P2016]）——
//    这类 bug 的好处是：**说清楚它算了什么之后，它的一切表现都是白送的推论。**

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

const int MAXN = 3005;
const int NEG = -1e9;
int n, m, pay[MAXN], sz[MAXN];
vector<pair<int, int>> son[MAXN];        // (儿子, 这条边的费用)
vector<vector<int>> f;

void dfs(int u) {
    if (u > n - m) {                     // 用户终端：一片叶子
        sz[u] = 1;
        f[u][0] = 0;
        f[u][1] = pay[u];
        return;
    }
    sz[u] = 0;
    f[u][0] = 0;
    for (auto& pr : son[u]) {
        int v = pr.first, c = pr.second;
        dfs(v);
        sz[u] += sz[v];
        for (int j = min(sz[u], m); j >= 1; j--)          // ← 倒序
            for (int k = 1; k <= min(sz[v], j); k++)
                if (f[u][j - k] > NEG / 2 && f[v][k] > NEG / 2)
                    f[u][j] = max(f[u][j], f[u][j - k] + f[v][k] - c);
    }
}

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 t = 0; t < k; t++) {
            int a, c;
            cin >> a >> c;
            son[i].push_back({a, c});
        }
    }
    for (int i = n - m + 1; i <= n; i++) cin >> pay[i];

    f.assign(n + 1, vector<int>(m + 1, 0));   // ← 这里
    dfs(1);

    int ans = 0;
    for (int j = m; j >= 0; j--) if (f[1][j] >= 0) { ans = j; break; }
    cout << ans << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★★ 说清楚它算了什么：它恒输出 M

初值一写成 0，「凑不出 j 个用户」和「凑出来不赚不亏」就成了同一件事 ⇒ 每一格都 ≥ 0 ⇒ 从大到小找第一个非负的格子，第一个就中 ⇒ 它恒输出 M。


它输出 `= M` 的轮数	★ 300 / 300
300 轮被抓	246
「正解 `< M`」的轮数	★ 246 —— 一个不差

⚠ 这是本章第三个「恒输出一个常量」的 bug： P1352 从 0 号找根恒输出 0、P2016 只换 min 恒输出 0、这一页恒输出 M。 ⇒ ★★ 它们的共同点是：说清楚「它算了什么」之后，抓获率、盲区、样例挡不挡得住全都是白送的推论，不用一条一条去试。

4★ 第三个错法：容量正序（样例放过了它）

p1273Fwd.cpp✗ j 从小到大枚举

// ✗ P1273：容量 j 写成了正序
//
// ⚠ 和 01 背包一维、和同题单的 [P2015] 是同一件事：正序时 `f[u][j-k]` 可能**已经用过这个儿子了**，
//    于是同一棵子树被算了两次 —— 同一批用户被数了两遍，钱也被收了两遍。
// ⇒ 它凭空造出根本不存在的方案 ⇒ 它报出来的用户数**恒 ≥ 正解**。

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

const int MAXN = 3005;
const int NEG = -1e9;
int n, m, pay[MAXN], sz[MAXN];
vector<pair<int, int>> son[MAXN];        // (儿子, 这条边的费用)
vector<vector<int>> f;

void dfs(int u) {
    if (u > n - m) {                     // 用户终端：一片叶子
        sz[u] = 1;
        f[u][0] = 0;
        f[u][1] = pay[u];
        return;
    }
    sz[u] = 0;
    f[u][0] = 0;
    for (auto& pr : son[u]) {
        int v = pr.first, c = pr.second;
        dfs(v);
        sz[u] += sz[v];
        for (int j = 1; j <= min(sz[u], m); j++)          // ← 正序（bug）
            for (int k = 1; k <= min(sz[v], j); k++)
                if (f[u][j - k] > NEG / 2 && f[v][k] > NEG / 2)
                    f[u][j] = max(f[u][j], f[u][j - k] + f[v][k] - c);
    }
}

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 t = 0; t < k; t++) {
            int a, c;
            cin >> a >> c;
            son[i].push_back({a, c});
        }
    }
    for (int i = n - m + 1; i <= n; i++) cin >> pay[i];

    f.assign(n + 1, vector<int>(m + 1, NEG));
    dfs(1);

    int ans = 0;
    for (int j = m; j >= 0; j--) if (f[1][j] >= 0) { ans = j; break; }
    cout << ans << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

同一棵子树被算了两次 ⇒ 凭空造出不存在的方案 ⇒ 恒 ≥ 正解（300 / 300），被抓 216 / 300。 ⚠ 官方样例原样放过它（都是 2）—— 和同题单的 P2015 一模一样：这一对「倒序」的坑，两道题的样例都挡不住。

5⚠⚠ 第四个「错法」根本不是错法 —— 草稿被实测打回来

草稿里我还写了一个：内层 k 从 0 开始（于是「一个用户都不服务的儿子」也照样付了那条线的钱）。理由听着很顺：白花钱 ⇒ 恒 ≤ 正解。

p1273Cost.cpp⚠ 看着像 bug —— 300 轮一次都没错

// ⚠ P1273：内层从 k = 0 开始枚举 —— 看着像 bug，**实测一个反例都没有**
//
// 草稿里我把它当成第三个错法写进来了，理由听着很顺：
// 「它允许花钱把信号送到一个中转站、那边却一个用户都不看 ⇒ 白花钱 ⇒ 恒 ≤ 正解」。
//
// ★★★ 300 轮实测：**被抓 0 轮**，它和正解**逐组相同**。一行就能证明为什么：
//
//     k = 0 那条转移是   f[u][j] = max(f[u][j], f[u][j-0] + f[v][0] - c)
//     而 f[v][0] 恒等于 0、c ≥ 1                 = max(f[u][j], f[u][j] - c)
//                                                = f[u][j]
//
// ⇒ 它加进来的那条转移**恒被 max 吃掉**，是一次空转。
// ⚠ 而「一个反例都没有」这句话是配了自检才敢写的：同一套度量程序在同一批数据上
//   抓到了另外两个 bug（246 轮和 39 轮）⇒ 它不是个空壳。

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

const int MAXN = 3005;
const int NEG = -1e9;
int n, m, pay[MAXN], sz[MAXN];
vector<pair<int, int>> son[MAXN];        // (儿子, 这条边的费用)
vector<vector<int>> f;

void dfs(int u) {
    if (u > n - m) {                     // 用户终端：一片叶子
        sz[u] = 1;
        f[u][0] = 0;
        f[u][1] = pay[u];
        return;
    }
    sz[u] = 0;
    f[u][0] = 0;
    for (auto& pr : son[u]) {
        int v = pr.first, c = pr.second;
        dfs(v);
        sz[u] += sz[v];
        for (int j = min(sz[u], m); j >= 1; j--)          // ← 倒序
            for (int k = 0; k <= min(sz[v], j); k++)   // ← 从 0 开始
                if (f[u][j - k] > NEG / 2 && f[v][k] > NEG / 2)
                    f[u][j] = max(f[u][j], f[u][j - k] + f[v][k] - c);
    }
}

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 t = 0; t < k; t++) {
            int a, c;
            cin >> a >> c;
            son[i].push_back({a, c});
        }
    }
    for (int i = n - m + 1; i <= n; i++) cin >> pay[i];

    f.assign(n + 1, vector<int>(m + 1, NEG));
    dfs(1);

    int ans = 0;
    for (int j = m; j >= 0; j--) if (f[1][j] >= 0) { ans = j; break; }
    cout << ans << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★★ 300 轮被抓 0 次，而且一行就能证明为什么

    k = 0 那条转移是   f[u][j] = max(f[u][j], f[u][j-0] + f[v][0] - c)
    而 f[v][0] 恒为 0、c ≥ 1          = max(f[u][j], f[u][j] - c)
                                      = f[u][j]

它加进来的那条转移恒被 max 吃掉，是一次空转 ⇒ 它和正解逐组相同。

⚠⚠ 而「一个反例都没有」这句话是配了自检才敢写的（P2240、P1094 那条通用规矩）：同一套度量程序、同一批数据，抓到了另外两个 bug（246 轮和 39 轮） ⇒ 它不是个空壳。

⇒ ★ 这一页和同题单的 P2015 凑成一对，两个方向都齐了：那儿是「我以为它只会往一个方向错，实测两个方向都错」，这儿是「我以为它是个 bug，实测它压根不改变任何东西」。 没量之前，两种判断都只是猜。

6★ 参照物、格式坑、规模

参照物是 2^M 枚举「让哪些用户看上」，把他们到根的路径并起来算一次成本 —— 「并起来」这三个字就是这道题，也正是第 ① 步那个贪心丢掉的东西。


300 轮：正解 vs `2^M` 枚举用户子集	★ 不一致 0 轮
顶格 `N = 3000`、单笔钱 `≤ 10` ⇒ 余额绝对值不超过	30 000 ⇒ `int` 够
树形背包 `O(n²)` ⇒ 顶格约	`9 × 10⁶` 次

⚠ 两个格式坑：① 用户编号是 N−M+1 … N，最后一行的 M 个数按编号顺序对上； ② 输入只列了 N−M 行（转播站），叶子那些行根本不存在 —— 按「读 N 行」写会卡在那儿。

p1273Brute.cpp参照物：2^M 枚举用户子集（300 轮不一致 0 轮）

7度量程序和生成器

⚠ 这道题的生成器比前几道难写：题面的编号规则把「谁是叶子」也定死了 —— 随手造一棵树再随便编号，多半会造出「一个中转站一个下级都没有」这种非法输入。 ⇒ 又一次第 13 章 P1162 那条：有一类题最难写的不是正解，是生成器。

p1273Count.cpp度量程序（本页所有数字都出自它）

p1273Gen.cpp数据生成器

8一页纸


★★ 关键的一步	用户数当容量、余额当价值：`f[u][j] = max(f[u][j−k] + f[v][k] − c)`；答案是最大的 `j` 使 `f[1][j] ≥ 0`
★ 第一版	按「净赚」排序 ⇒ 丢掉了成本共享 ⇒ 合法方案 ⇒ 恒 ≤ 正解，被抓 39/300
★★★ 初值写成 0	「恰好」变成「至多」⇒ 恒输出 M；被抓 246 ≡ 正解 < M 的 246 轮
★ 容量正序	恒 ≥ 正解，被抓 216/300；⚠ 样例放过（和 P2015 一样）
⚠⚠ 第四个不是 bug	`k` 从 0 开始 ⇒ 那条转移恒被 `max` 吃掉，300 轮 0 次（配了自检）
参照物	`2^M` 枚举用户子集＋路径取并；300 轮不一致 0 轮
⚠ 格式	用户编号 `N−M+1 … N`；输入只有 `N−M` 行，叶子那些行不存在
规模	`N ≤ 3000` ⇒ 余额 ≤ 30 000（`int` 够）、`O(n²)` 约 `9 × 10⁶` 次

洛谷 P1273 有线电视网

0题目原文（本地存了一份）

样例解释

输入

输出

1★ 第一版：按「自己出的钱减去自己那条路的成本」排个序

2★★ 关键的一步：状态里存的是余额，而「几个用户」当容量

3★★★ 第二个错法：初值写成 0 —— 本章第三个「恒输出一个常量」

4★ 第三个错法：容量正序（样例放过了它）

5⚠⚠ 第四个「错法」根本不是错法 —— 草稿被实测打回来

6★ 参照物、格式坑、规模

7度量程序和生成器

8一页纸