P2016 战略游戏 · 习题解析｜信息学奥赛算法练功房

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

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

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

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

题目背景

Bob 喜欢玩电脑游戏，特别是战略游戏。但是他经常无法找到快速通关游戏的办法，现在他有个问题。

题目描述

他要建立一个古城堡，城堡中的路形成一棵无根树。他要在这棵树的结点上放置最少数目的士兵，使得这些士兵能瞭望到所有的路。

注意，某个士兵在一个结点上时，与该结点相连的所有边将都可以被瞭望到。

请你编一程序，给定一棵树，帮 Bob 计算出他需要放置最少的士兵。

输入格式

第一行一个整数 n，表示树中结点的数目。

第二行至第 n+1 行，每行描述每个结点信息，依次为：一个整数 i，代表该结点标号，一个自然数 k，代表后面有 k 条无向边与结点 i 相连。接下来 k 个整数，分别是每条边的另一个结点标号 r₁, r₂, …, r_k，表示 i 与这些点间各有一条无向边相连。

对于一个 n 个结点的树，结点标号在 0 到 n−1 之间，在输入数据中每条边只出现一次。保证输入是一棵树。

输出格式

输出文件仅包含一个整数，为所求的最少的士兵数目。

说明/提示

数据规模与约定

对于全部的测试点，保证 1 ≤ n ≤ 1500。

输入输出样例

输入

输出

四个点：1 号连着 0、2、3。只要在 1 号放一个士兵，三条路全都看得见 ⇒ 答案 1。

⚠ 读一下输入的形状：不是一行一条边，是「一行一个点的整张邻接表」，而且每条边只出现一次（这里挂在 0 和 1 那两行上）—— 所以读进来之后两头都要挂，否则树是断的。

1★ 第一版：把上一道题的转移「max 换成 min」照抄过来

题单上就写着这两道题「是一对反着的」：P1352 求最大，这道题求最小。于是最真实的第一版是把上一道的两行转移原样搬来，把 max 改成 min：

p2016MinOnly.cpp✗ 第一版：只把 max 换成了 min

// ✗ P2016 第一版：把 P1352 的转移「max 换成 min」直接照抄过来
//
//   f[u][0] = Σ min(f[v][0], f[v][1])      ← 照抄「下属来不来都行」
//   f[u][1] = 1 + Σ min(f[v][0], f[v][1])
//
// ★ 它算了什么：两头都不放也被算成合法 ⇒「每条边至少有一个端点被选」这个限制
//    **被整个写没了** ⇒ 它恒输出 0。
//    （和 P1352 正文第八条恒等式是同一个形状：一个 bug 把约束抹掉，答案退化成一个常量。）

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

const int MAXN = 1505;
int n;
vector<int> adj[MAXN];
int f[MAXN][2];

void dfs(int u, int fa) {
    f[u][0] = 0;
    f[u][1] = 1;
    for (int v : adj[u]) {
        if (v == fa) continue;
        dfs(v, u);
        f[u][0] += min(f[v][0], f[v][1]);    // ← 这一行就是那个 bug
        f[u][1] += min(f[v][0], f[v][1]);
    }
}

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

    if (!(cin >> n) || n <= 0) return 0;
    for (int t = 0; t < n; t++) {
        int i, k;
        cin >> i >> k;
        for (int j = 0; j < k; j++) { int r; cin >> r; adj[i].push_back(r); adj[r].push_back(i); }
    }
    dfs(0, -1);
    cout << min(f[0][0], f[0][1]) << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

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

f[u][0] = Σ min(f[v][0], f[v][1]) 这一行，允许「u 不放、v 也不放」—— 边 (u, v) 就没人管了。也就是说，「每条边至少要有一个端点被选」这个限制被整个写没了。一个限制都没有的最小化问题，答案当然是 0。


300 轮它输出 0 的轮数	★ 300 / 300
300 轮被抓	300 / 300

⇒ 这和 P1352 正文第 ⑨ 步那个「儿子也能来」是同一个形状的 bug：一个字之差把约束抹掉，答案退化成一个常量。 ★★ 而这类 bug 有个共同的好处 —— 它们的一切表现都是白送的推论，不用一条一条去试。

2★★ 关键的一步：变的不是符号，是那一项的结构

★ 两道题并排看，只有一处真的不一样

    P1352（最大快乐指数）        P2016（最少士兵）

    f[u][0] = Σ max(f[v][0],     f[u][0] = Σ f[v][1]
                    f[v][1])                 ^^^^^^^ 必须选！
    f[u][1] = r[u] + Σ f[v][0]   f[u][1] = 1 + Σ min(f[v][0], f[v][1])

f[u][0]（u 不放士兵）：那些边 (u, v) 只剩 v 能管了 ⇒ v 必须放，没有「取较优的」这个自由；
f[u][1]（u 放了士兵）：边 (u, v) 已经有人管，v 放不放都行 ⇒ 这才是取 min 的地方。

⇒ ★★ 所以「反着的题」这句话只对了一半：max → min 是表面，真正变的是「下属有没有选择权」这件事在哪一行。

p2016.cpp★ 这一版就能 AC

// P2016 战略游戏 —— 正解：树形 DP，O(n)
//
// 要的是**最小点覆盖**：选最少的点，让每条边至少有一个端点被选。
//
//   f[u][0] = u 不放士兵时，u 的子树里最少要放几个
//   f[u][1] = u   放士兵时，同上
//
//   f[u][0] = Σ f[v][1]                    ★ u 不放 ⇒ 边 (u,v) 只能由 v 来管 ⇒ v 必须放
//   f[u][1] = 1 + Σ min(f[v][0], f[v][1])  u 放了 ⇒ 边 (u,v) 已经有人管，v 随意
//
// ⚠ 和 [P1352 没有上司的舞会] 只差两处，但**不是「把 max 换成 min」那么简单**：
//    f[u][0] 那一项从「取较优的」变成了「必须选」—— 结构变了，不只是符号变了。
//
// ⚠ 两个和算法无关的坑：结点编号是 0 ~ n-1（P1352 是 1 ~ n），
//    而且输入不是「一行一条边」，是「一行一个点的整张邻接表」。

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

const int MAXN = 1505;
int n;
vector<int> adj[MAXN];
int f[MAXN][2];

void dfs(int u, int fa) {
    f[u][0] = 0;
    f[u][1] = 1;
    for (int v : adj[u]) {
        if (v == fa) continue;
        dfs(v, u);
        f[u][0] += f[v][1];                  // u 不放，v 必须放
        f[u][1] += min(f[v][0], f[v][1]);    // u 放了，v 随意
    }
}

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

    if (!(cin >> n) || n <= 0) return 0;
    for (int t = 0; t < n; t++) {
        int i, k;
        cin >> i >> k;
        for (int j = 0; j < k; j++) {
            int r;
            cin >> r;
            adj[i].push_back(r);             // 每条边只给一次，两头都要挂上
            adj[r].push_back(i);
        }
    }

    dfs(0, -1);                              // 无根树，随便挑 0 号当根
    cout << min(f[0][0], f[0][1]) << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

3★★★ 第二个错法：另一半也照抄了上一道题

上一道是「u 来了，下属一个都不能来」。照抄过来就成了「u 放了士兵，下属就不放了」：

p2016NoBoth.cpp✗ 「u 放了，下属就不放」

// ✗ P2016：另一半也照抄了 P1352 —— 「u 放了士兵，他的下属就不用放了」
//
//   f[u][1] = 1 + Σ f[v][0]      ← 照抄「u 来了，下属一个都不能来」
//
// ★ 它算了什么：它多加了一条题目根本没有的限制（相邻两个点不能都放士兵），
//    ⇒ 它解的是一个**收紧了的问题** ⇒ 恒 ≥ 正解。
// ⚠ 这一份和 p2016MinOnly.cpp 是一对：一个把限制写没了（恒 ≤，而且恒等于 0），
//    一个凭空多加了限制（恒 ≥）。两份都源自「上一道题是怎么写的」。

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

const int MAXN = 1505;
int n;
vector<int> adj[MAXN];
int f[MAXN][2];

void dfs(int u, int fa) {
    f[u][0] = 0;
    f[u][1] = 1;
    for (int v : adj[u]) {
        if (v == fa) continue;
        dfs(v, u);
        f[u][0] += f[v][1];
        f[u][1] += f[v][0];                  // ← 这一行就是那个 bug
    }
}

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

    if (!(cin >> n) || n <= 0) return 0;
    for (int t = 0; t < n; t++) {
        int i, k;
        cin >> i >> k;
        for (int j = 0; j < k; j++) { int r; cin >> r; adj[i].push_back(r); adj[r].push_back(i); }
    }
    dfs(0, -1);
    cout << min(f[0][0], f[0][1]) << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★★ 它被抓的轮数 ≡「没有任何一个最小覆盖是独立集」的轮数 —— 一个不差

它凭空加了一条题目根本没有的限制（相邻两个点不能都放士兵）⇒ 它解的是一个收紧了的问题 ⇒ 恒 ≥ 正解（300 / 300）。

那它什么时候才真的错？只有当这棵树的每一个最小点覆盖里都存在相邻的两个点时。 把这句话直接数出来（n = 12，300 轮）：


它 ≥ 正解	300 / 300
它被抓	105
「没有任何一个最小覆盖是独立集」的轮数	★ 105 —— 一个不差

最小的例子只要六个点：a 和 b 相邻，a 挂着两片叶子，b 也挂着两片叶子。唯一的二元覆盖是 {a, b}，而它们相邻 ⇒ 这份错法只能用三个士兵。

4★★ 第三个错法：反复挑度数最大的点（点覆盖上最有名的贪心）

p2016Greedy.cpp✗ 每次挑「还连着最多条没被管住的边」的点

// ✗ P2016 的另一个第一反应：反复挑「还连着最多条没被管住的边」的那个点
//
// 这是点覆盖问题上最有名的贪心。在一般图上它是个近似算法（能差到 log 倍），
// 在树上它也不对 —— 本页量了它多久错一次、错的时候差多少。
// ★ 它给出的是一个**真的覆盖了所有边的方案** ⇒ 恒 ≥ 正解，永远不会少报。

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

const int MAXN = 1505;
int n;
vector<int> adj[MAXN];

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

    if (!(cin >> n) || n <= 0) return 0;
    vector<pair<int, int>> es;
    for (int t = 0; t < n; t++) {
        int i, k;
        cin >> i >> k;
        for (int j = 0; j < k; j++) {
            int r; cin >> r;
            adj[i].push_back(r); adj[r].push_back(i);
            es.push_back({i, r});
        }
    }

    vector<char> dead(es.size(), 0), taken(n, 0);
    int cnt = 0;
    while (true) {
        vector<int> deg(n, 0);
        for (size_t e = 0; e < es.size(); e++)
            if (!dead[e]) { deg[es[e].first]++; deg[es[e].second]++; }
        int best = -1;
        for (int u = 0; u < n; u++) if (best < 0 || deg[u] > deg[best]) best = u;
        if (best < 0 || deg[best] == 0) break;
        taken[best] = 1;
        cnt++;
        for (size_t e = 0; e < es.size(); e++)
            if (!dead[e] && (es[e].first == best || es[e].second == best)) dead[e] = 1;
    }
    cout << cnt << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

它给出的是一个真的覆盖了所有边的方案 ⇒ 恒 ≥ 正解（300 / 300），被抓 35 / 300，错的时候平均多用 20.86% 个士兵，最多多用 40.00%。

★★★ 而形状这把旋钮，又一次把两个 bug 推向相反方向

树的形状（各 300 轮）	只换 min	「下属不放」	贪心
随机树	300	105	35
链	300	★ 精确的 0	121
菊花	300	★ 精确的 0	★ 精确的 0

链上「下属不放」是精确的 0：一条链上总能隔一个选一个 ⇒ 总存在一个本身就是独立集的最小覆盖，那条多余的限制一分钱都不花。
链上贪心反而更容易被抓（35 → 121）：链上处处度数是 2，贪心挑谁全凭编号，很容易挑歪。
菊花上两个一起隐身：中心点度数最大，贪心第一步就挑中它，而它就是唯一的最优解。

⇒ ★★★ 同一把旋钮把两个 bug 推向相反方向 —— 这是本页第二次（同题单的 P1352 上是「有没有负数」那把旋钮），也是本书量到的第六、七次。「换个形状再跑一遍」永远要连着「哪个 bug」一起说。

5★★★ 参照物：走一条和树形 DP 一行代码都不共享的路

★ 树是二分图 ⇒ König 定理 ⇒ 最小点覆盖 = 最大匹配

按深度奇偶给结点染色，树的每条边都跨色 ⇒ 树一定是二分图。而二分图上有 König 定理：最小点覆盖的大小 = 最大匹配的大小。

最大匹配用匈牙利算法（一条一条找增广路）算出来，里头没有「子树」、没有「后序」、没有 f[u][0/1] —— 它和正解只在答案上相遇。


300 轮：树形 DP vs `2ⁿ` 枚举	★ 不一致 0 轮
300 轮：树形 DP vs König（最大匹配）	★ 300 / 300 对上

⇒ 这就是本书那条「验算最好走一条和算法完全无关的路」（P1147、P1966、P1332）在这一章的现场。 ⚠ 而且它比「我又写了一遍 DP」有说服力得多：后者错一次就错两遍。

p2016Match.cpp参照物②：König（二分图最大匹配），300 / 300 对上

p2016Brute.cpp参照物①：2ⁿ 枚举放士兵的点（300 轮不一致 0 轮）

6⚠ 和算法无关、却真会挂人的两条

结点编号是 0 ~ n−1 —— 而同一张题单上一道 P1352 是 1 ~ n。两道题挨着写，编号基这件事必须每道题重新问一遍； ⇒ 那一页有个错法（找根的循环从 0 写起）来处就在这儿。
输入不是「一行一条边」，是一行一个点的邻接表，而且每条边只出现一次 —— 读进来必须两头都挂（adj[i].push_back(r) 和 adj[r].push_back(i)），只挂一头的话，从 0 号点 DFS 下去会走不到大半棵树。

规模：n ≤ 1500 ⇒ 2ⁿ 枚举只能当小数据的参照物；正解是 O(n)，答案上界就是 n，int 绰绰有余。

7度量程序和生成器

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

p2016Gen.cpp数据生成器

8一页纸


★★ 关键的一步	`f[u][0] = Σ f[v][1]` —— `u` 不放，下属就没有选择权；变的不是 `max → min`
★★★ 第一版	只把 `max` 换成 `min` ⇒ 限制被写没了 ⇒ 恒输出 0（300/300）
★★★ 第二个错法	「`u` 放了下属就不放」恒 ≥ 正解，被抓 105 ≡「没有独立的最小覆盖」的 105 轮
★★ 第三个错法	度数最大贪心：恒 ≥ 正解，被抓 35/300，错时平均多用 20.86%
★★★ 形状旋钮	链：「下属不放」精确的 0，贪心 35 → 121（相反方向）；菊花：两个一起 0
★★★ 参照物	König 定理：树是二分图 ⇒ 最小点覆盖 = 最大匹配，和 DP 一行不共享，300/300 对上
⚠ 两个格式坑	编号 `0 ~ n−1`（上一道是 `1 ~ n`）；邻接表输入，每条边只给一次 ⇒ 两头都要挂

洛谷 P2016 战略游戏

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

数据规模与约定

输入

输出

1★ 第一版：把上一道题的转移「max 换成 min」照抄过来

2★★ 关键的一步：变的不是符号，是那一项的结构

3★★★ 第二个错法：另一半也照抄了上一道题

4★★ 第三个错法：反复挑度数最大的点（点覆盖上最有名的贪心）

5★★★ 参照物：走一条和树形 DP 一行代码都不共享的路

6⚠ 和算法无关、却真会挂人的两条

7度量程序和生成器

8一页纸