P3959 宝藏 · 习题解析｜信息学奥赛算法练功房

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

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

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

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

题目背景

NOIP2017 D2T2

题目描述

参与考古挖掘的小明得到了一份藏宝图，藏宝图上标出了 n 个深埋在地下的宝藏屋，也给出了这 n 个宝藏屋之间可供开发的 m 条道路和它们的长度。

小明决心亲自前往挖掘所有宝藏屋中的宝藏。但是，每个宝藏屋距离地面都很远，也就是说，从地面打通一条到某个宝藏屋的道路是很困难的，而开发宝藏屋之间的道路则相对容易很多。

小明的决心感动了考古挖掘的赞助商，赞助商决定免费赞助他打通一条从地面到某个宝藏屋的通道， 通往哪个宝藏屋则由小明来决定。

在此基础上，小明还需要考虑如何开凿宝藏屋之间的道路。已经开凿出的道路可以任意通行不消耗代价。每开凿出一条新道路，小明就会与考古队一起挖掘出由该条道路所能到达的宝藏屋的宝藏。另外，小明不想开发无用道路，即两个已经被挖掘过的宝藏屋之间的道路无需再开发。

新开发一条道路的代价是 L × K。其中 L 代表这条道路的长度， K 代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的宝藏屋的数量（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋）。

请你编写程序为小明选定由赞助商打通的宝藏屋和之后开凿的道路，使得工程总代价最小，并输出这个最小值。

输入格式

第一行两个用空格分离的正整数 n, m，代表宝藏屋的个数和道路数。

接下来 m 行，每行三个用空格分离的正整数，分别是由一条道路连接的两个宝藏屋的编号（编号为 1 ~ n），和这条道路的长度 v。

输出格式

一个正整数，表示最小的总代价。

说明/提示

P3959 样例解释

样例解释 1：小明选定让赞助商打通了 1 号宝藏屋。开发道路 1 → 2 挖掘 2 号，开发 1 → 4 挖掘 4 号，还开发了 4 → 3 挖掘 3 号。工程总代价为 1 × 1 + 1 × 1 + 1 × 2 = 4。

样例解释 2：小明同样从 1 号开挖，但这次开发的是 1 → 2、1 → 3、1 → 4。工程总代价为 1 × 1 + 3 × 1 + 1 × 1 = 5。

数据规模与约定

对于 20% 的数据：保证输入是一棵树，1 ≤ n ≤ 8，v ≤ 5 × 10³ 且所有的 v 都相等；
对于 40% 的数据：1 ≤ n ≤ 8，0 ≤ m ≤ 10³，v ≤ 5 × 10³ 且所有的 v 都相等；
对于 70% 的数据：1 ≤ n ≤ 8，0 ≤ m ≤ 10³，v ≤ 5 × 10³；
对于 100% 的数据：1 ≤ n ≤ 12，0 ≤ m ≤ 10³，v ≤ 5 × 10⁵。

upd 2022.7.27：新增加 50 组 Hack 数据。

输入输出样例

输入

输出

就是上图那四个点。答案 4。

⚠ 这一组样例三个错法一个都没挡住（根固定 4、MST 4、没乘 dep 3 —— 前两个原样打出 4）。 ★ 而样例 ② 只改了一条边的长度（3 4 1 → 3 4 2），答案就从 4 变成 5 —— 出题人给两组样例，从来不是同一件事的重复。

1★ 第一版：这不就是最小生成树吗

p3959Mst.cpp✗ 第一版：求 MST，再按题面规则计费

// ✗ P3959 第一版：求最小生成树
//
// 这是几乎所有人的第一反应：「把所有点连起来、总长最小」不就是 MST 吗？
// ★ 它忽略了那个 **× K** —— 代价不是边长本身，而是「边长 × 它在第几层」。
// ⚠ 而 MST 给出的是**一个真能施工的方案**（一棵树），所以它的**边集**合法；
//   可它按题目的计费规则算出来的钱**不一定最小** ——
//   这一页量了它多久错一次、错的时候差多少。
//
// （为了公平，这一版拿到 MST 之后，会枚举每个根、按题面规则算出这棵树的最小代价。）

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = LLONG_MAX / 4;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<vector<ll>> d(n, vector<ll>(n, INF));
    for (int i = 0; i < n; i++) d[i][i] = 0;
    for (int e = 0; e < m; e++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        u--; v--;
        d[u][v] = min(d[u][v], w);
        d[v][u] = min(d[v][u], w);
    }
    // Prim 求 MST
    vector<char> in(n, 0);
    vector<ll> key(n, INF);
    vector<int> par(n, -1);
    key[0] = 0;
    vector<pair<int, int>> tree;
    for (int it = 0; it < n; it++) {
        int u = -1;
        for (int v = 0; v < n; v++) if (!in[v] && (u < 0 || key[v] < key[u])) u = v;
        if (u < 0 || key[u] >= INF) { cout << 0 << '\n'; return 0; }
        in[u] = 1;
        if (par[u] >= 0) tree.push_back({par[u], u});
        for (int v = 0; v < n; v++)
            if (!in[v] && d[u][v] < key[v]) { key[v] = d[u][v]; par[v] = u; }
    }
    // 拿这棵树，枚举每个根，按题面规则算代价
    vector<vector<int>> adj(n);
    for (auto& e : tree) { adj[e.first].push_back(e.second); adj[e.second].push_back(e.first); }
    ll best = INF;
    for (int r = 0; r < n; r++) {
        vector<int> dep(n, 0), st{r};
        vector<char> vis(n, 0);
        vis[r] = 1; dep[r] = 1;
        ll cost = 0;
        while (!st.empty()) {
            int u = st.back(); st.pop_back();
            for (int v : adj[u]) if (!vis[v]) {
                vis[v] = 1; dep[v] = dep[u] + 1;
                cost += d[u][v] * dep[u];
                st.push_back(v);
            }
        }
        best = min(best, cost);
    }
    cout << (best >= INF ? 0 : best) << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★ 它忽略的正是那个 × K —— 而它错得「不常见但不轻」

「把所有点连起来、总长最小」是 MST；可这道题的代价是 L × K —— 同一条边，挖得越晚越贵。于是「总边长最小」和「总代价最小」不是一回事：有时候宁可多花一点边长，换一棵更矮的树。

★ 为了公平，这一版拿到 MST 之后还枚举了每个根、按题面规则算出这棵树的最小代价。它给出的是一棵真能施工的树 ⇒ 恒 ≥ 正解。


它 ≥ 正解	★ 300 / 300
300 轮被抓	110
错的时候平均多花	15.63%
最多多花	56.76%

⚠ 注意这个组合：只有三分之一的轮次会错，但错的时候能差一半以上 —— 和第 20 章 P1048 那个「81% 的轮次是对的、错的时候只差 10%」正好是两种不同的骗法。

2★★ 关键的一步：状态里除了集合，还要有「第几层」

★ f[dep][S] —— 而转移要枚举子集

    f[dep][S] = 已经挖通的宝藏屋集合是 S、当前正在挖第 dep 层时的最小代价

    转移：枚举 S 之外的非空子集 T（这一层新挖出来的那一批）
          代价 = dep × Σ_{v ∈ T} (v 连到 S 里某个点的最短边)

为什么要有 dep：代价里的 K 就是深度 ⇒ 不知道现在挖到第几层，就算不出这一批的钱。这和本章正文里「状态要带上后面还会用到的那一点信息」是同一条道理。

★★ 枚举子集的写法是这一章的招牌：

for (int T = rest; T; T = (T - 1) & rest)     // rest = 全集 ^ S

「所有 S 的所有子集」加起来正好是 3ⁿ（每一位有「在 T / 在 S\T / 都不在」三种）—— 实测 n = 12 时跑了 541 052 次，而 3¹² = 531 441，比值 1.02（多出来的是外层那点开销）。 ⇒ 这条「加起来是 3ⁿ」的性质是可以量出来验的，不用只当结论背。

p3959.cpp★ 这一版就能 AC

// P3959 宝藏 —— 正解：状压 DP ＋ **分层**，O(3ⁿ × n)
//
// ★ 代价是 L × K，K 是「从起点到这条路起点经过的宝藏屋数」——
//   也就是说**同一条边，挖得越晚越贵**。所以状态里必须有「现在挖到第几层」。
//
//   f[dep][S] = 已经挖通的宝藏屋集合是 S、当前正在挖第 dep 层时的最小代价
//   转移：枚举 S 的**子集** T（这一层新挖出来的那一批），
//         代价 = dep × Σ_{v ∈ T} (v 到 S\T 里某个点的最短边)
//
// ★★ 枚举子集的写法 `for (T = S; T; T = (T-1) & S)` 是这一章的招牌 ——
//    所有 S 的所有子集加起来正好是 **3ⁿ**（每一位有「在 T / 在 S\T / 都不在」三种），
//    n = 12 时 3¹² = 53 万，随便跑。
//
// ⚠ 三个坑：
//   ① 起点要**枚举**（题面让你自己选一个宝藏屋通到地面）；
//   ② 同一对点可能有**重边**，只留最短的；
//   ③ 代价上界：11 条边 × 5×10⁵ × 层数 12 ⇒ 6.6×10⁷，`int` 够，但中间量用 long long 更省心。

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

const ll INF = LLONG_MAX / 4;

int n, m;
ll d[13][13];

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

    if (!(cin >> n >> m)) return 0;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) d[i][j] = (i == j) ? 0 : INF;
    for (int e = 0; e < m; e++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        u--; v--;
        d[u][v] = min(d[u][v], w);              // ← ② 重边只留最短的
        d[v][u] = min(d[v][u], w);
    }

    int full = (1 << n) - 1;
    // cost[S][T]：从已挖通的集合 S 出发，把 T 里每个点各接一条最短边进来的总长
    // （T 与 S 不相交；只要有一个点接不上就作废）
    vector<vector<ll>> add(1 << n, vector<ll>(n, INF));
    for (int S = 0; S <= full; S++)
        for (int v = 0; v < n; v++) {
            if (S >> v & 1) continue;
            ll best = INF;
            for (int u = 0; u < n; u++)
                if ((S >> u & 1) && d[u][v] < INF) best = min(best, d[u][v]);
            add[S][v] = best;
        }

    vector<vector<ll>> f(n + 1, vector<ll>(1 << n, INF));
    for (int s = 0; s < n; s++) f[1][1 << s] = 0;      // ← ① 枚举起点，它是第 1 层

    ll ans = INF;
    for (int dep = 1; dep <= n; dep++)
        for (int S = 0; S <= full; S++) {
            if (f[dep][S] >= INF) continue;
            if (S == full) { ans = min(ans, f[dep][S]); continue; }
            int rest = full ^ S;
            for (int T = rest; T; T = (T - 1) & rest) {     // ★ 枚举 S 之外的非空子集
                ll sum = 0;
                bool ok = true;
                for (int v = 0; v < n && ok; v++) {
                    if (!(T >> v & 1)) continue;
                    if (add[S][v] >= INF) ok = false;
                    else sum += add[S][v];
                }
                if (!ok) continue;
                ll nv = f[dep][S] + sum * dep;              // ★ 这一层的边都乘 dep
                if (nv < f[dep + 1][S | T]) f[dep + 1][S | T] = nv;
            }
        }

    cout << (ans >= INF ? 0 : ans) << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

3★★★ 第二个错法：没枚举起点 —— 而题面那句话就摆在那儿

p3959Root1.cpp✗ 直接从 1 号宝藏屋开挖

// ✗ P3959：没枚举起点，直接从 1 号宝藏屋开挖
//
// ★ 题面写着「通往哪个宝藏屋则由小明来决定」—— 起点是**你选的**，不是给定的。
//   固定成 1 号 ⇒ 它解的是一个**收紧了的问题** ⇒ 代价**恒 ≥ 正解**。
// ⚠ 又一次「[第 27 章 P1352](/sol/p1352/) 的根要自己找」在这一章的变体：
//   那道题的根是**输入里推出来的**，这道题的根是**你要枚举的**。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = LLONG_MAX / 4;
int n, m;
ll d[13][13];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m)) return 0;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i][j] = (i == j) ? 0 : INF;
    for (int e = 0; e < m; e++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        u--; v--;
        d[u][v] = min(d[u][v], w);
        d[v][u] = min(d[v][u], w);
    }
    int full = (1 << n) - 1;
    vector<vector<ll>> add(1 << n, vector<ll>(n, INF));
    for (int S = 0; S <= full; S++)
        for (int v = 0; v < n; v++) {
            if (S >> v & 1) continue;
            ll best = INF;
            for (int u = 0; u < n; u++) if ((S >> u & 1) && d[u][v] < INF) best = min(best, d[u][v]);
            add[S][v] = best;
        }
    vector<vector<ll>> f(n + 1, vector<ll>(1 << n, INF));
    f[1][1] = 0;                                  // ← 只从 1 号开挖
    ll ans = INF;
    for (int dep = 1; dep <= n; dep++)
        for (int S = 0; S <= full; S++) {
            if (f[dep][S] >= INF) continue;
            if (S == full) { ans = min(ans, f[dep][S]); continue; }
            int rest = full ^ S;
            for (int T = rest; T; T = (T - 1) & rest) {
                ll sum = 0;
                bool ok = true;
                for (int v = 0; v < n && ok; v++) {
                    if (!(T >> v & 1)) continue;
                    if (add[S][v] >= INF) ok = false; else sum += add[S][v];
                }
                if (!ok) continue;
                ll nv = f[dep][S] + sum * dep;
                if (nv < f[dep + 1][S | T]) f[dep + 1][S | T] = nv;
            }
        }
    cout << (ans >= INF ? 0 : ans) << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

题面写着「通往哪个宝藏屋则由小明来决定」—— 起点是你选的。固定成 1 号 ⇒ 收紧了的问题 ⇒ 恒 ≥ 正解（300 / 300），被抓 214 / 300。 ⚠ 而官方样例放过了它（那两组样例的最优起点恰好就是 1 号）。

⇒ 这是第 27 章 P1352「根要自己找」在这一章的变体：那道题的根是从输入里推出来的，这道题的根是你要枚举的 —— ★ 两种都不是「默认 1 号」。

4★ 第三个错法：忘了乘 dep —— 它算的是一个有名字的量

p3959NoDep.cpp✗ 代价直接用边长

// ✗ P3959：忘了乘那个 dep（把代价当成边长本身）
//
// ★ 它算的就是**最小生成树的总边长** —— 一个和题面无关的量。
//   ⇒ 它恒 ≤ 正解（每条边至少乘 1）。这一页顺手验了这条恒等式。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = LLONG_MAX / 4;
int n, m;
ll d[13][13];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n >> m)) return 0;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i][j] = (i == j) ? 0 : INF;
    for (int e = 0; e < m; e++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        u--; v--;
        d[u][v] = min(d[u][v], w);
        d[v][u] = min(d[v][u], w);
    }
    int full = (1 << n) - 1;
    vector<vector<ll>> add(1 << n, vector<ll>(n, INF));
    for (int S = 0; S <= full; S++)
        for (int v = 0; v < n; v++) {
            if (S >> v & 1) continue;
            ll best = INF;
            for (int u = 0; u < n; u++) if ((S >> u & 1) && d[u][v] < INF) best = min(best, d[u][v]);
            add[S][v] = best;
        }
    vector<vector<ll>> f(n + 1, vector<ll>(1 << n, INF));
    for (int s = 0; s < n; s++) f[1][1 << s] = 0;
    ll ans = INF;
    for (int dep = 1; dep <= n; dep++)
        for (int S = 0; S <= full; S++) {
            if (f[dep][S] >= INF) continue;
            if (S == full) { ans = min(ans, f[dep][S]); continue; }
            int rest = full ^ S;
            for (int T = rest; T; T = (T - 1) & rest) {
                ll sum = 0;
                bool ok = true;
                for (int v = 0; v < n && ok; v++) {
                    if (!(T >> v & 1)) continue;
                    if (add[S][v] >= INF) ok = false; else sum += add[S][v];
                }
                if (!ok) continue;
                ll nv = f[dep][S] + sum;             // ← 少乘了 dep
                if (nv < f[dep + 1][S | T]) f[dep + 1][S | T] = nv;
            }
        }
    cout << (ans >= INF ? 0 : ans) << '\n';
    return 0;
}

点一下即可编辑

输入（stdin）

输出

点「运行 ▶」看结果

★★ 说清楚它算了什么：它就是最小生成树的总边长

每条边至少乘 1 ⇒ 它恒 ≤ 正解（300 / 300）。而它到底算了什么？


它 ≡ MST 的总边长	★ 300 / 300，一个不差
而它真被抓	⚠ 284 / 300
另外那 16 轮	★ 它恰好蒙对 —— 最优树只有一层，每条边都乘 1

⚠ 那 16 轮是我自己撞出来的：断言先按「恒等式成立 ⇒ 必被抓 300」写了 300，一跑就红。 ⇒ ★★ 「它算的是另一个量」推不出「它一定和正解不同」 —— 两个不同的量在某些输入上会取到同一个值，而那个「某些」得数出来。

⇒ 又一次「说清楚一个 bug 算了什么，比说它错了有用得多」—— 本轮第三次（另外两次是 P1879 的「漏掉 S=0」、P1171 的「不回起点」）。

★ 而它和第 ① 步那个 MST 版正好是一对： 一个用 MST 的树形但按题面计费（恒 ≥），一个按题面搜树形但忘了计费（恒 ≤，且恰好等于 MST 边长）。

5★★ 题面那三档数据范围，各是一件什么工具

★ 「所有的 v 都相等」——造一档试试它是情报、命门还是噪声

题面给了四档数据范围，其中 20% 和 40% 那两档都写着「所有的 v 都相等」。按第 12 章那套判据，造一档符合它的数据看行为变没变：

各 300 轮	默认档（边权随机）	边权全相等（题面 40% 那档）
正解 vs 暴力不一致	0	0
「根固定为 1 号」被抓	214	156
「拿 MST 当答案」被抓	110	90

两个 bug 都还在，只是更难抓一点 ⇒ 那句话是情报（出题人分档送分用的），不是命门，也不完全是噪声 —— 它降低了抓获率但没消掉任何 bug。

★ 而另外两档是实打实的工具：n ≤ 8 那两档意味着暴力枚举「根 + 生成树」在那儿跑得动 （本页参照物就是它）；n ≤ 12 那一档才逼出 3ⁿ 的枚举子集。 ⇒ 又一次「题面上那几行数字，每一行都是一件工具」。

⚠ 而有一件题面「没说」的事：重边

题面从头到尾没保证「两个宝藏屋之间最多一条道路」。造一档故意带重边的数据（300 轮里 300 轮真的有重边）：正解仍然 0 轮不一致 —— 因为读入时对每一对点只留了最短的那条（d[u][v] = min(d[u][v], w)）。

⇒ ★ 这一句是主动防，不是踩过坑才加的：题面没保证的事，就当它会发生。

6★ 参照物和规模

参照物是枚举「根 + 生成树」：枚举加点顺序（第一个就是根），每个点在已加入的点里选一个父亲，照题面 L × K 逐条边算钱。n ≤ 6 跑得动 —— 而题面 20%/40%/70% 三档都是 n ≤ 8， 出题人已经把「暴力能拿多少分」写在题面上了。


300 轮：正解 vs 枚举「根 + 生成树」	★ 不一致 0 轮
顶格 `n = 12` 的枚举子集次数	541 052（`3¹² = 531 441`，比值 1.02）
代价上界	11 条边 × `5×10⁵` × 12 层 ⇒ `6.6 × 10⁷` ⇒ `int` 够（中间量仍用 `long long` 省心）

p3959Brute.cpp参照物：枚举根 + 生成树（300 轮不一致 0 轮）

7度量程序和生成器

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

p3959Gen.cpp数据生成器

8一页纸


★★ 关键的一步	`f[dep][S]` —— 代价是 `L × K`，同一条边挖得越晚越贵，所以状态要有「第几层」
★★ 招牌写法	`for (T = rest; T; T = (T-1) & rest)`；所有子集加起来 = `3ⁿ`（实测 541052 vs 531441）
★ 第一版	MST ⇒ 恒 ≥ 正解，被抓 110/300、错时平均多花 15.63%、最多 56.76%
★★★ 没枚举起点	收紧了的问题 ⇒ 恒 ≥ 正解，被抓 214/300；⚠ 两组样例都放过它
★ 忘了乘 `dep`	恒 ≤ 正解，且 ≡ MST 的总边长（300/300 一个不差）
★★ 「所有 v 都相等」	是情报：两个 bug 都还在，只是抓获率从 214/110 降到 156/90
⚠ 题面没保证的事	重边 —— 读入时对每对点只留最短的（造 300 轮带重边的数据验过，0 不一致）

洛谷 P3959 宝藏

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

输入

输出

1★ 第一版：这不就是最小生成树吗

2★★ 关键的一步：状态里除了集合，还要有「第几层」

3★★★ 第二个错法：没枚举起点 —— 而题面那句话就摆在那儿

4★ 第三个错法：忘了乘 dep —— 它算的是一个有名字的量

5★★ 题面那三档数据范围，各是一件什么工具

6★ 参照物和规模

7度量程序和生成器

8一页纸