买礼物

形式化题目

给定 $B$ 个对象，每个对象可以用代价 $A$ 独立获得；若已获得对象 $i$ ，则对象 $j$ 可以用代价 $K_{i,j}$ 获得。求获得全部对象的最小总代价。

思路

先看一个直接按购买状态做的小数据暴力：

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// brute.cpp：状压 DP 直接模拟购买顺序。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 12;
const int INF = 1e9;

int direct_cost, gift_cnt;
int discount[MAXN][MAXN];
int dp[1 << MAXN];

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

    cin >> direct_cost >> gift_cnt;
    for (int i = 0; i < gift_cnt; i++) {
        for (int j = 0; j < gift_cnt; j++) {
            cin >> discount[i][j];
        }
    }

    int max_mask = 1 << gift_cnt;
    for (int i = 0; i < max_mask; i++) {
        dp[i] = INF;
    }
    dp[0] = 0;

    for (int mask = 0; mask < max_mask; mask++) {
        if (dp[mask] == INF) {
            continue;
        }

        for (int j = 0; j < gift_cnt; j++) {
            if ((mask >> j) & 1) {
                continue;
            }

            int cost = direct_cost;
            for (int i = 0; i < gift_cnt; i++) {
                if (((mask >> i) & 1) == 0) {
                    continue;
                }
                cost = min(cost, discount[i][j]);
            }

            int next_mask = mask | (1 << j);
            dp[next_mask] = min(dp[next_mask], dp[mask] + cost);
        }
    }

    cout << dp[max_mask - 1] << '\n';

    return 0;
}

暴力用状态压缩 DP 表示“已经买了哪些礼物”。每次从未购买的礼物中选一个，要么直接花 $A$ ，要么从已购买礼物里找一个最便宜的优惠价。这个做法能忠实模拟购买过程，但状态数是 $2^B$ ，只能处理很小的 $B$ 。

每件礼物最终是怎么被买到的？

把购买过程抽象一下：除了第一件礼物，每件礼物都是“接到”已经买好的集合上。这个接入方式只有两类：

text

1
2直接买礼物 j：       花 A
通过礼物 i 买 j：    花 K[i][j]

如果我们只关心“每件礼物通过哪条方式接进来”，而不关心具体购买顺序，那么这很像在选一些边，把所有礼物连成一个整体。

直接买也能看成一条边吗？

可以。加一个虚拟源点 $S$ ，表示“从商店原价买”。

text

1
2S -- j       权值 A        表示直接买第 j 件礼物
i -- j       权值 K[i][j]  表示已买 i 后，用优惠价买 j

这张图展示样例 2 的建图方式：

text

1
2
3
4
5
6
7
8
9       2
  1 -------- 2
  | \        |
3 |  \4      | 2
  |   \      |
  S -------- 3
       3

还有 S--1, S--2, S--3 三条权值为 3 的边。

从图上看，买齐所有礼物就是让 $S$ 和所有礼物点连通。选择的边权总和就是总花费。因此问题变成：

在“虚拟源点 + 礼物点”的图中，选一棵连接所有点的最小生成树。

为什么是最小生成树？

任意合法购买方案都能看成一组边：每件礼物第一次被买到时，要么连向 $S$ ，要么连向之前某件已买礼物。这样所有礼物一定都和 $S$ 连通。

反过来，图中的任意一棵连通所有点的树也对应一种购买方式：从 $S$ 出发，沿树边逐步扩展，遇到 S--j 就直接买，遇到 i--j 就在买到 $i$ 后用优惠价买 $j$ 。所以“最小花费购买方案”和“最小权连通结构”是同一个问题。

如果选出的边里有环，删掉环上一条边仍然保持连通，并且不会增加费用。因此最优解一定可以是一棵树。最小的这种树就是 MST。

为什么用 Prim 更自然？

输入给的是完整的 $B \times B$ 优惠矩阵， $B \le 500$ 。不需要真的把所有边拿出来排序。Prim 的含义正好贴合购买过程：

text

1min_cost[j] = 当前把礼物 j 接入已买集合的最低代价

初始时，每件礼物都可以直接买，所以：

text

1min_cost[j] = A

每次选择 min_cost 最小的未选礼物接入；接入礼物 u 后，再用 K[u][v] 尝试更新其它礼物的接入代价。

text

1
2
3
4
5已买集合 S
  ↓
选一个最便宜接入的礼物 u
  ↓
用 u 的优惠价更新所有未买礼物 v

注意 $K_{i,j}=0$ 表示没有优惠，不能当成一条 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/**
 * 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-08-10 21:46
 * update_at: 2026-08-10 21:46
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXB = 505;
const int INF = 1e9;

int direct_cost;              // 直接购买任意一件礼物的价格 A
int gift_cnt;                 // 礼物数量 B
int discount[MAXB][MAXB];     // discount[i][j]：已买 i 后买 j 的优惠价，0 表示无优惠
int min_cost[MAXB];           // 当前把礼物 i 接入已买集合的最小代价
bool selected[MAXB];          // selected[i] 表示礼物 i 已经接入生成树

int prim() {
    for (int i = 1; i <= gift_cnt; i++) {
        // 初始时，每件礼物都可以直接买，相当于从虚拟源点连一条权值 A 的边。
        min_cost[i] = direct_cost;
        selected[i] = false;
    }

    int answer = 0;

    for (int step = 1; step <= gift_cnt; step++) {
        int u = 0;
        for (int i = 1; i <= gift_cnt; i++) {
            if (selected[i]) continue;
            if (u == 0 || min_cost[i] < min_cost[u]) {
                u = i;
            }
        }

        selected[u] = true;
        answer += min_cost[u];

        // 用新接入的礼物 u 去更新其它礼物的最小接入代价。
        for (int v = 1; v <= gift_cnt; v++) {
            if (selected[v]) continue;
            if (discount[u][v] == 0) continue; // 0 表示没有优惠边
            if (discount[u][v] < min_cost[v]) {
                min_cost[v] = discount[u][v];
            }
        }
    }

    return answer;
}

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

    cin >> direct_cost >> gift_cnt;
    for (int i = 1; i <= gift_cnt; i++) {
        for (int j = 1; j <= gift_cnt; j++) {
            cin >> discount[i][j];
        }
    }

    cout << prim() << '\n';
    return 0;
}

复杂度

Prim 每次选一个新礼物，并扫描一整行优惠价更新其它礼物。礼物数为 $B$ ，时间复杂度 $O(B^2)$ ，空间复杂度 $O(B^2)$ 。

总结

本题关键不是 Prim 模板本身，而是建模：把“直接买”看成从虚拟源点连边，把“优惠买”看成礼物之间连边。这样购买过程就变成了把所有点连通的最小代价问题，也就是最小生成树。

目录

形式化题目

思路

代码

复杂度

总结