《P1194 买礼物》
题目描述
又到了一年一度的明明生日了，明明想要买 B 样东西，巧的是，这 B 样东西价格都是 A 元。
但是，商店老板说最近有促销活动，也就是：
如果你买了第 I 样东西，再买第 J 样，那么就可以只花 KI,J 元，更巧的是，KI,J 竟然等于 KJ,I。
现在明明想知道，他最少要花多少钱。
输入格式
第一行两个整数，A,B。
接下来 B 行，每行 B 个数，第 I 行第 J 个为 KI,J。
我们保证 KI,J=KJ,I 并且 KI,I=0。
特别的，如果 KI,J=0，那么表示这两样东西之间不会导致优惠。
注意 KI,J 可能大于 A。
输出格式
一个整数，为最小要花的钱数。
输入输出样例
输入 #1复制
1 1 0
输出 #1复制
1
输入 #2复制
3 3 0 2 4 2 0 2 4 2 0
输出 #2复制
7
说明/提示
样例解释 2。
先买第 2 样东西，花费 3 元，接下来因为优惠，买 1,3 样都只要 2 元，共 7 元。
（同时满足多个“优惠”的时候，聪明的明明当然不会选择用 4 元买剩下那件，而选择用 2 元。）
数据规模
对于 30% 的数据，1≤B≤10。
对于 100% 的数据，1≤B≤500,0≤A,KI,J≤1000。
2018.7.25新添数据一组
代码实现：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAX_ITEMS = 501; // 最大物品数量
const int INF = 0x7fffffff; // 表示无穷大
int discountMatrix[MAX_ITEMS][MAX_ITEMS]; // 物品间的优惠价格矩阵
int minDist[MAX_ITEMS]; // 记录到最小生成树的最短距离
bool inMST[MAX_ITEMS]; // 标记物品是否已加入最小生成树
int main()
{
// freopen("present.in","r",stdin);
int basePrice, itemCount; // 基础价格和物品数量
cin >> basePrice >> itemCount;
// 读取优惠价格矩阵并进行初始化处理
for (int i = 1; i <= itemCount; i++) {
for (int j = 1; j <= itemCount; j++) {
cin >> discountMatrix[i][j];
// 自己到自己的价格设为无穷大（无意义）
if (i == j) {
discountMatrix[i][j] = INF;
continue;
}
// 如果没有优惠(K=0)，则使用基础价格
if (discountMatrix[i][j] == 0) {
discountMatrix[i][j] = basePrice;
}
// 保证无向图的对称性
discountMatrix[j][i] = discountMatrix[i][j];
}
}
// 初始化距离数组
for (int i = 1; i <= itemCount; i++) {
minDist[i] = INF;
}
minDist[1] = 0; // 从第一个物品开始
// Prim算法构建最小生成树
for (int i = 1; i <= itemCount; i++) {
// 找到距离当前生成树最近的物品
int currentMin = INF;
int selectedItem = -1;
for (int j = 1; j <= itemCount; j++) {
if (minDist[j] < currentMin && !inMST[j]) {
currentMin = minDist[j];
selectedItem = j;
}
}
// 将选中的物品加入生成树
inMST[selectedItem] = true;
// 更新其他物品到生成树的最短距离
for (int j = 1; j <= itemCount; j++) {
if (discountMatrix[selectedItem][j] < minDist[j] && !inMST[j]) {
minDist[j] = discountMatrix[selectedItem][j];
}
}
}
// 计算总花费：所有边的距离和加上第一个物品的基础价格
int totalCost = 0;
for (int i = 1; i <= itemCount; i++) {
totalCost += minDist[i];
}
totalCost += basePrice;
cout << totalCost << endl;
return 0;
}