洛谷P1194题：利用Kruskal算法求解商品优惠组合问题
22小时前
一、题目解读
洛谷P1194题要求计算在给定商品单价及优惠组合价格的情况下，购买所有商品的最小总价。题目关键在于如何处理优惠关系，并将其转化为图论中的边权重问题，进而通过算法寻找最优解。
二、解题思路
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. 路径压缩优化并查集查询效率，提升整体性能。
原创内容 转载请注明出处
