P1194 买礼物（黄色普及/提高-）

MST, https://www.luogu.com.cn/problem/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 1
0

输出 #1

输入输出样例 #2

输入 #2

输出 #2

说明/提示

样例解释 $2$ 。

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

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

数据规模

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

对于 $100 %$ 的数据， $1 \leq B \leq 500, 0 \leq A, K_{I, J} \leq 1000$ 。

2018.7.25新添数据一组

这是一道典型的最小生成树（Minimum Spanning Tree, MST）问题。

算法分析

我们可以将购买每件物品的过程抽象为一个图：

虚拟节点：引入一个虚拟源点 0，代表“直接购买”。从节点 0 向每个物品节点 $i$ （ $1 \leq i \leq B$ ）连一条权重为 $A$ 的边，表示以原价 $A$ 直接购买物品 $i$ 。
物品间优惠：对于任意两件物品 $I$ 和 $J$ ，如果存在优惠价格 $K_{I, J}$ 且 $K_{I, J} > 0$ ，则在节点 $I$ 和 $J$ 之间连一条权重为 $K_{I, J}$ 的无向边。
求解：由于我们需要买齐所有 $B$ 样物品，并且希望总花费最小。这相当于在包含虚拟源点 0 和所有物品节点组成的图（共 $B + 1$ 个节点）中，求一棵包含所有节点的最小生成树。最小生成树的边数刚好为 $B$ ，其权值之和即为最少花费。

我们可以使用 Kruskal 算法 来解决此问题：

将所有边按权重从小到大排序。
使用并查集（Union-Find）维护连通性。
依次选择权重最小且不构成环的边，直到选择了 $B$ 条边。

Python 3 实现代码

python

import sys

def solve():
    # 读取所有输入数据
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    A = int(input_data[0])
    B = int(input_data[1])
    
    edges = []
    
    # 1. 建立虚拟源点 0 到所有物品的边，权重为原价 A
    for i in range(1, B + 1):
        edges.append((A, 0, i))
        
    # 2. 读取优惠矩阵，建立物品之间的边
    idx = 2
    for i in range(1, B + 1):
        for j in range(1, B + 1):
            k = int(input_data[idx])
            idx += 1
            # 只考虑有优惠（k > 0）且避免重复添加无向边（i < j）
            if i < j and k > 0:
                edges.append((k, i, j))
                
    # 将所有边按权值从小到大排序
    edges.sort()
    
    # 并查集初始化
    parent = list(range(B + 1))
    
    def find(x):
        path = []
        while parent[x] != x:
            path.append(x)
            x = parent[x]
        for node in path:
            parent[node] = x
        return x
        
    def union(x, y):
        root_x = find(x)
        root_y = find(y)
        if root_x != root_y:
            parent[root_x] = root_y
            return True
        return False
        
    # Kruskal 算法求最小生成树
    total_cost = 0
    edges_count = 0
    
    for w, u, v in edges:
        if union(u, v):
            total_cost += w
            edges_count += 1
            # 当构建了 B 条边时，说明 B+1 个节点已全部连通
            if edges_count == B:
                break
                
    print(total_cost)

if __name__ == '__main__':
    solve()

复杂度分析

时间复杂度：
- 构建边集的时间复杂度为 $O (B^{2})$ 。
- 排序边集的时间复杂度为 $O (E \log E)$ ，其中边数 $E \leq B + \frac{B (B - 1)}{2}$ 约为 $1.25 \times 10^{5}$ 。
- 并查集操作接近 $O (1)$ 。
- 整体时间复杂度为 $O (B^{2} \log B)$ ，在 $B \leq 500$ 的数据规模下，可以高效运行完毕。
空间复杂度：
- 存储边集需要 $O (B^{2})$ 的空间，并查集需要 $O (B)$ 的空间，整体空间复杂度为 $O (B^{2})$ ，内存占用极小。

P1194 买礼物（黄色 普及/提高-） ​

P1194 买礼物（黄色普及/提高-）