买礼物

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

把直接买建成虚拟源点边，把优惠价建成礼物间边，转化为最小生成树。

OJ: luogu

题目 ID: P1194

难度:普及

标签:图论最小生成树Prim建模

创建: 2026-06-20 00:55

更新: 2026-10-21 14:20

前置题目
luogu P1546[USACO3.1] 最短网络 Agri-NetB 的 Prim 主循环原样复用 A 教的「维护最小连边代价、每次选代价最小者加入、再用新点更新其它点」这一步（B 自述“关键不是 Prim 模板本身，而是建模”），再叠加 A 未教的虚拟源点把直接买/优惠买建成 MST 的建模。roj 1350【例4-11】最短网络(agrinet)B 的 Prim 主循环与 A 逐句同构：min_cost 即 dis，接入新礼物 u 后用 K[u] 行做一遍 min 松弛；A 教的这一步正是 B 主解法的骨架，B 仅叠加虚拟源点建模roj 1349【例4-10】最优布线问题B 的 Prim 直接复用 A 教的「维护到已接入点集的最便宜接入边 + 用新接入点那一行松弛」这一步，只把初值改成虚拟源点的 A 并跳过 0 边，再在其上叠加虚拟源点建模
后置题目
luogu P4180[BJWC2010] 严格次小生成树A 教的 Kruskal（并查集按边权升序选边）正是 B 的第一步；B 在其上叠加「枚举非树边 + 树上换边」与倍增 LCA 维护路径最值。

目录

  1. 形式化题目
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

给定 BB 个对象，每个对象可以用代价 AA 独立获得；若已获得对象 ii，则对象 jj 可以用代价 Ki,jK_{i,j} 获得。求获得全部对象的最小总代价。

思路

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

cpp
/**
 * 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-10-21 14:35
 */
// brute.cpp：小数据暴力解，用状态压缩 DP 直接模拟购买顺序，用来独立验证 main.cpp。
// 状态 mask 表示"已经买了哪些礼物"。转移时选一件未买的 j，
// 代价取「直接买 A」与「从已买的某件 i 用优惠价买 K[i][j]」的最小值。
//
// 关键细节：K[i][j] == 0 表示这两件礼物之间没有优惠，不是免费的边。
// 若把 0 也拿去取 min，会误以为可以免费连锁购买（例如 3 件礼物、全 0 矩阵时
// 会算出 3 而不是正确的 9）。
//
// 与 main.cpp 的最小生成树建模完全不共享实现，因此适合用来独立验证。
// 状态数 2^B，只在 B 很小时可用。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 12;  // 只枚举极小数据：B <= 8 较稳妥
const int INF = 1e9;

int direct_cost;  // 直接买任意一件礼物的价格 A
int gift_cnt;     // 礼物数量 B
int discount[MAXN][MAXN];  // discount[i][j]：已买 i 后买 j 的优惠价，0 表示无优惠

int dp[1 << MAXN];  // dp[mask]：买齐 mask 中这些礼物的最小花费

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;  // i 还没买，用不上它的优惠
                if (discount[i][j] == 0) continue;      // 0 表示没有优惠，不是免费
                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 表示“已经买了哪些礼物”。每次从未购买的礼物中选一个，要么直接花 AA，要么从已购买礼物里找一个最便宜的优惠价。这个做法能忠实模拟购买过程，但状态数是 2B2^B，只能处理很小的 BB。

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

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

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

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

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

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

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

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

text
       2
  1 -------- 2
  | \        |
3 |  \4      | 2
  |   \      |
  S -------- 3
       3

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

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

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

为什么是最小生成树？

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

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

为什么最优解一定无环？ 若选中的边里有环，删掉环上任一条，连通性不变，总代价只会减少或不变。所以最优的那组边一定无环；连通且无环就是树。

“总能排出购买顺序”靠什么保证？ 树连通，所以从 SS 做 BFS 能到达所有礼物，按 BFS 序购买时每个点的父节点必已买好。这就是为什么“选哪些边”和“按什么顺序买”是同一件事。

所以最优的那组边构成一棵树，最便宜的那棵就是 MST。

为什么用 Prim 更自然？

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

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

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

text
min_cost[j] = A

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

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

注意 Ki,j=0K_{i,j}=0 表示没有优惠，不能当成一条 0 元边；代码里需要跳过这种情况。若误当成免费边，全 0 矩阵且 A=3A=3、B=3B=3 时会算出 3（误以为能免费连锁），而正确答案是 3×3=93\times3=9。

代码

cpp
/**
 * 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-10-21 14:35
 */
// 买礼物：每件礼物可花 A 元直接买；若已买 i，则买 j 只需 K[i][j] 元。求买齐全部的最小花费。
// 建模：加虚拟源点 S（编号 B+1）表示"从商店原价买"，于是
//   S -- j       权 A          直接买第 j 件
//   i -- j       权 K[i][j]    已买 i 后，用优惠价买 j
// 买齐全部 = 让 S 和所有礼物点连通，总花费 = 选中边的权和，所以是最小生成树。
// 最优解一定无环：有环就删掉环上任一条，连通性不变、代价不增，于是连通且无环即为树。
// 反向也成立：树连通，从 S 做 BFS 能到达所有礼物，按 BFS 序购买时父节点必已买好。
// 注意 K[i][j] = 0 表示"没有优惠"，必须当无边跳过，不能当 0 权边（否则会误以为能免费连锁）。
// 这里用 Kruskal：边数约 B^2/2 + B，B <= 500 时最多约 12.5 万条，按边权排序后扫描即可。
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;

// 一条无向边：从 u 连到 v，边权 w。点编号 1..n，n >= 1。
// 点编号要当数组下标用，写成 int；边权和可能很大，用 ll。
struct Edge {
    int u;  // 起点
    int v;  // 终点
    ll w;   // 边权
};

// 边权小的排在前面，Kruskal 每次都先试当前最小的边。
bool cmp_edge(const Edge &a, const Edge &b) {
    return a.w < b.w;
}

// 找 x 所在集合的根，顺路把路径上的点直接挂到根上（路径压缩）。
int dsu_find(vector<int> &dsu_parent, int x) {
    if (dsu_parent[x] == x) return x;
    dsu_parent[x] = dsu_find(dsu_parent, dsu_parent[x]);
    return dsu_parent[x];
}

// 合并 a、b 所在的两个集合；两端本来就连通时返回 false。
// dsu_size[x] 是 x 当根时该集合的点数，用来按大小合并。
bool dsu_merge(vector<int> &dsu_parent, vector<int> &dsu_size, int a, int b) {
    int root_a = dsu_find(dsu_parent, a);
    int root_b = dsu_find(dsu_parent, b);
    if (root_a == root_b) return false;
    // 小集合接到大集合下面，配合路径压缩，单次操作接近常数。
    if (dsu_size[root_a] < dsu_size[root_b]) swap(root_a, root_b);
    dsu_parent[root_b] = root_a;
    dsu_size[root_a] += dsu_size[root_b];
    return true;
}

// 求最小生成树，按值接收边表，排序不会打乱调用者的边表顺序。
// 返回 true：图连通，answer 存 MST 的总权值；
// 返回 false：图不连通，没有生成树，answer 无意义。
bool kruskal(int n, vector<Edge> edges, ll &answer) {
    sort(edges.begin(), edges.end(), cmp_edge);

    // 并查集要跟着 n 开，放在函数里比固定大小的全局数组安全。
    vector<int> dsu_parent(n + 1);   // dsu_parent[x]：x 的父节点，x 是根时等于 x
    vector<int> dsu_size(n + 1, 1);  // dsu_size[x]：x 是根时集合的大小
    for (int i = 1; i <= n; i++) dsu_parent[i] = i;

    answer = 0;
    int selected = 0;  // 已选边数，一棵生成树正好要 n - 1 条

    for (const Edge &edge : edges) {
        // 自环、两端已经连通的边都会成环，不能选。
        if (!dsu_merge(dsu_parent, dsu_size, edge.u, edge.v)) continue;
        answer += edge.w;
        selected++;
        if (selected == n - 1) break;
    }

    return selected == n - 1;  // 单点图选 0 条边：连通，答案为 0
}

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

    int direct_cost;  // 直接买任意一件礼物的价格 A
    int gift_cnt;     // 礼物数量 B
    cin >> direct_cost >> gift_cnt;

    int source = gift_cnt + 1;  // 虚拟源点 S，表示"从商店原价买"
    vector<Edge> edges;
    edges.reserve(gift_cnt * gift_cnt);  // 优惠边最坏 B*(B-1)/2 条，加 B 条源点边

    // S 到每件礼物：权 A，表示直接买
    for (int j = 1; j <= gift_cnt; j++) {
        edges.push_back({source, j, direct_cost});
    }

    // 礼物之间的优惠边：只取上三角，矩阵对称不必重复建
    for (int i = 1; i <= gift_cnt; i++) {
        for (int j = 1; j <= gift_cnt; j++) {
            int price;
            cin >> price;
            if (i >= j) continue;      // 对角线 K[i][i]=0 与下三角都跳过
            if (price == 0) continue;  // 0 表示没有优惠，当无边处理
            edges.push_back({i, j, price});
        }
    }

    ll answer = 0;
    // 所有礼物都有一条到 S 的边，所以这张图必然连通，返回值一定为 true
    kruskal(source, edges, answer);
    cout << answer << '\n';

    return 0;
}

复杂度

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

总结

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

两个容易被跳过的细节：最优解一定无环（有环可删边不增代价），以及 K=0K=0 必须当“无边”而不是“免费边”。