洛谷P1194题：利用Kruskal算法求解商品优惠组合问题

一、题目解读

洛谷P1194题要求计算在给定商品单价及优惠组合价格的情况下，购买所有商品的最小总价。题目关键在于如何处理优惠关系，并将其转化为图论中的边权重问题，进而通过算法寻找最优解。

二、解题思路

采用经典的Kruskal算法求解最小生成树。核心思路如下：

1. 虚拟节点构建：引入节点0作为“起点”，与所有商品建立边，权重为商品单价，将问题转化为从0出发覆盖所有节点的最小路径和。

2. 优惠边筛选：仅保留i<j的优惠边（避免重复），降低计算复杂度。

3. Kruskal算法：对边按权重排序，通过并查集逐步合并连通分量，直至生成包含B条边的树。

三、解题步骤

1. 输入与初始化：读入商品数量B和单价A，初始化边集edges及并查集parent。

2. 构建虚拟边：添加{0,i,A}边至edges，确保每个商品与虚拟节点相连。

3. 读入优惠边：若i<j且存在优惠价格k，添加{i,j,k}至edges。

4. 排序与Kruskal：

    按边权重排序edges。

    遍历边集，若合并u和v节点未形成环，则计入总价并更新并查集。

    当连通分量达到B时终止，总价为最小生成树权重。

四、代码与注释

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 边结构（节点u,v，权重w）
struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const {
        return w < other.w;   // 按权重排序
    }
};

vector<int> parent;   // 并查集父节点数组

// 并查集查找根节点
int find(int x) {
    return parent[x] == x? x : parent[x] = find(parent[x]);  // 路径压缩
}

int main() {
    int A, B;   // A：商品单价，B：商品数量
    cin >> A >> B;
    
    vector<Edge> edges;   // 存储所有边
    
    // 步骤2：添加虚拟节点0到各商品的边
    for (int i = 1; i <= B; ++i) {
        edges.push_back({0, i, A});
    }
    
    // 步骤3：读入优惠价格
    for (int i = 1; i <= B; ++i) {
        for (int j = 1; j <= B; ++j) {
            int k;
            cin >> k;
            if (i < j && k!= 0) {  // 避免重复添加
                edges.push_back({i, j, k});
            }
        }
    }
    
    // Kruskal算法准备
    sort(edges.begin(), edges.end());   // 步骤4：排序
    parent.resize(B + 1);  
    for (int i = 0; i <= B; ++i) parent[i] = i;   // 初始化并查集
    
    int total = 0, count = 0;
    for (auto& e : edges) {
        int rootU = find(e.u);
        int rootV = find(e.v);
        if (rootU!= rootV) {
            parent[rootV] = rootU;   // 合并节点
            total += e.w;
            if (++count == B) break;  // 生成树有B条边
        }
    }
    
    cout << total << endl;
    return 0;
}

五、总结

本解法通过巧妙引入虚拟节点，将商品购买问题转化为最小生成树问题，结合Kruskal算法高效求解。关键在于：

1. 利用并查集优化连通性判断，避免重复计算。

2. 边权重排序与剪枝（仅保留i<j的优惠边）降低时间复杂度。

3. 路径压缩优化并查集查询效率，提升整体性能。