买礼物

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

把“原价买一件礼物”看成从虚拟源点连一条权值 A 的边，把优惠价看成礼物之间的边权，原题就转化成一棵最小生成树。

OJ: luogu

题目 ID: P1194

难度:普及+/提高

标签:图论最小生成树贪心

日期: 2026-06-20 00:55

目录

  1. 题意
    1. 样例图
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结
  6. 一图流解析

题意

有 B 件礼物，每件礼物如果直接买都要 A 元。

但如果已经买过第 i 件，再买第 j 件，就可以用优惠价 K[i][j] 购买，而且同时有多个优惠时可以选最便宜的那个。

问把所有礼物都买下来，最少要花多少钱。

样例图

这张图把样例 2 画成“虚拟源点 + 礼物点”的形式：

graph G {
  S -- 1 [label="3"];
  S -- 2 [label="3"];
  S -- 3 [label="3"];
  1 -- 2 [label="2"];
  2 -- 3 [label="2"];
  1 -- 3 [label="4"];
}

先直接买第 2 件礼物花 3 元，再通过优惠买 1 和 3 各花 2 元，总价就是 7。 从这张图也能看出来，这正好对应选了一棵最便宜的连通结构。

思路

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

cpp
// 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
  • 如果已经买过一些礼物，就可以从这些礼物里挑一个最便宜优惠价

这个思路很好理解，但礼物数一大就不能状压了。

关键观察是：每件礼物最终都要以某种方式“接入”已经买过的集合里，而这个接入方式只有两类：

  1. 直接原价买，代价是 A
  2. 通过某件已买礼物的优惠接进来，代价是 K[i][j]

于是可以加一个虚拟源点 S：

  • S -> i 连一条权值为 A 的边，表示“第 i 件礼物直接买”
  • 礼物 i 和礼物 j 之间连一条权值 K[i][j] 的边，表示“通过优惠买”

这样，想把所有礼物都买到手，就等价于：

从虚拟源点出发，把所有礼物点连起来，并让总边权最小。

这就是最小生成树。

因为输入本身就是一个完整矩阵，直接写 Prim 最自然：

  1. 初始时，所有礼物到生成树的代价都设成 A
  2. 每次选一个当前最便宜接入的礼物
  3. 再用它的优惠价更新其它礼物的接入代价

代码

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

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

int direct_cost, gift_cnt;
int discount[MAXN][MAXN];
int dist_to_tree[MAXN];
bool vis[MAXN];

int prim() {
    for (int i = 1; i <= gift_cnt; i++) {
        dist_to_tree[i] = direct_cost;
        vis[i] = false;
    }

    int answer = 0;

    for (int i = 1; i <= gift_cnt; i++) {
        int u = 0;
        for (int j = 1; j <= gift_cnt; j++) {
            if (vis[j]) {
                continue;
            }
            if (u == 0 || dist_to_tree[j] < dist_to_tree[u]) {
                u = j;
            }
        }

        vis[u] = true;
        answer += dist_to_tree[u];

        for (int v = 1; v <= gift_cnt; v++) {
            if (vis[v]) {
                continue;
            }
            if (discount[u][v] < dist_to_tree[v]) {
                dist_to_tree[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;
}

复杂度

设礼物数量为 B。

Prim 每次找一个新点，再扫一整行更新最优接入代价：

  • 时间复杂度 O(B2)O(B^2)
  • 空间复杂度 O(B2)O(B^2)

总结

这题最重要的一步，是把“直接买”也看成一种边。只要想到加一个虚拟源点，把原价 A 变成源点到每件礼物的边，原题就会很自然地落到最小生成树上。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

一图流解析