P1194

买礼物

题目描述

又到了一年一度的明明生日了，明明想要买 $B$ 样东西，巧的是，这 $B$ 样东西价格都是 $A$ 元。

但是，商店老板说最近有促销活动，也就是：

如果你买了第 $I$ 样东西，再买第 $J$ 样，那么就可以只花 $K_{I,J}$ 元，更巧的是， $K_{I,J}$ 竟然等于 $K_{J,I}$ 。

现在明明想知道，他最少要花多少钱。

输入格式

第一行两个整数， $A,B$ 。

接下来 $B$ 行，每行 $B$ 个数，第 $I$ 行第 $J$ 个为 $K_{I,J}$ 。

我们保证 $K_{I,J}=K_{J,I}$ 并且 $K_{I,I}=0$ 。

特别的，如果 $K_{I,J}=0$ ，那么表示这两样东西之间不会导致优惠。

注意 $K_{I,J}$ 可能大于 $A$ 。

输出格式

一个整数，为最小要花的钱数。

输入输出样例

输入样例 #1

1 1
0

输出样例 #1

输入样例 #2

输出样例 #2

说明/提示

样例解释 $2$ 。

先买第 $2$ 样东西，花费 $3$ 元，接下来因为优惠，买 $1,3$ 样都只要 $2$ 元，共 $7$ 元。

（同时满足多个“优惠”的时候，聪明的明明当然不会选择用 $4$ 元买剩下那件，而选择用 $2$ 元。）

数据规模

对于 $30\%$ 的数据， $1\le B\le 10$ 。

对于 $100\%$ 的数据， $1\le B\le500,0\le A,K_{I,J}\le1000$ 。

2018.7.25新添数据一组

题解

1 篇题解

登录后即可使用 Markdown 发布题解。

YuyiLv.6👑 站长管理员

P1194 买礼物题解 Author: Yuyi 题意分析明明要买 $B$ 样东西，原价都是 $A$ 元。但如果买了 $I$ 再买 $J$，就可以享受 $K {I,J}$ 的优惠价。我们要让花的最少，这就等价于图论中经典的“ 超级源点 + 最小生成树 ”模型！我们可以假设存在一个编号为 $0$ 的“原价商店”（超级源点）： 1. 0 号点连向每一个物…

点击展开完整题解点击收起题解

2026年8月9日 22:23

P1194 买礼物题解

Author: Yuyi

题意分析

明明要买 $B$ 样东西，原价都是 $A$ 元。但如果买了 $I$ 再买 $J$ ，就可以享受 $K_{I,J}$ 的优惠价。我们要让花的最少，这就等价于图论中经典的“超级源点 + 最小生成树”模型！我们可以假设存在一个编号为 $0$ 的“原价商店”（超级源点）：

0 号点连向每一个物品点 $1 \dots B$ ，边权就是直接购买的原价 $A$ 。
物品点互相之间如果存在优惠价 $K_{I,J}$ ，且这个优惠价比原价 $A$ 还要便宜（即 $0 < K_{I,J} \le A$ ），我们就给这两点连一条权值为 $K_{I,J}$ 的边。只要用 Kruskal 算法在这张图里求出一棵包含 $0 \dots B$ 共计 $B+1$ 个点的最小生成树，其总权值就是我们要的最小花费！

正解代码及分析

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
#define lowbit(a) (a)&(-a)
using namespace std;
const int maxn = 125505; // 按照最大边数 B+B*B/2 统一调配
const int mo = 998244353;
const double pi = acos(-1.0);
template <typename T>
inline void read(T &X)
{
    X = 0;int w = 0; char ch = 0;
    while(!isdigit(ch)) {w |= ch == '-' ;ch = getchar();}
    while(isdigit(ch)) X = X * 10 + (ch^48),ch = getchar();
    if(w) X = -X;
}
int a,b;
struct Edge
{
    int u,v;
    int w;
}e[maxn];
bool cmp(Edge A,Edge B)
{
    return A.w < B.w;
}
int fa[maxn];
int find(int u)
{
    if(u == fa[u]) return u;
    return fa[u] = find(fa[u]);
}
void solve()
{
    read(a),read(b);
    int m = 0;
    rep(i,1,b)
    {
        m++;
        e[m].u = 0;
        e[m].v = i;
        e[m].w = a; // 0号源点代表直接用原价买
    }
    rep(i,1,b)
    {
        rep(j,1,b)
        {
            int k;
            read(k);
            if(i < j && k != 0 && k <= a) // 超过原价的无效优惠直接扔掉
            {
                m++;
                e[m].u = i;
                e[m].v = j;
                e[m].w = k;
            }
        }
    }
    rep(i,0,b) fa[i] = i; // 注意有0号点参与
    sort(e+1,e+1+m,cmp);
    int cnt = 0;
    ll ans = 0;
    rep(i,1,m)
    {
        int fu = find(e[i].u);
        int fv = find(e[i].v);
        if(fu != fv)
        {
            fa[fu] = fv;
            ans += e[i].w;
            cnt++;
        }
        if(cnt == b) break; // B+1个点的MST恰好需要B条边
    }
    cout << ans << endl;
    return;
}
int main()
{
    int T=1;
//  freopen("mul.in","r",stdin);
//  freopen("mul.out","w",stdout);
//  read(T);
    while(T--) solve();
    return 0;
}

复杂度分析

时间复杂度：建图时读取完整的 $B \times B$ 矩阵，耗时 $O(B^2)$ 。符合条件的边最多大约有 $\frac{B^2}{2}$ 条，因此排序耗时为 $O(B^2 \log B)$ 。后续的 Kruskal 并查集合并复杂度近乎常数，耗时 $O(B^2)$ 。综合时间复杂度为 $O(B^2 \log B)$ ，对于 $B \le 500$ 而言极其迅速。
空间复杂度：存储的边数最大规模不到 13万，严格遵守统一规范，将并查集数组 fa 和边集数组 e 一起定义在了 maxn = 125505，整体耗费的空间不过一两兆，空间复杂度 $O(B^2)$ ，稳妥无比。

讨论

0 条讨论

登录后即可使用 Markdown 发起讨论和回复。

还没有讨论，来发起第一条吧。

买礼物