【题目来源】
洛谷：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
0
【输出样例】
1
【算法标签】
《洛谷 P1194 买礼物》 #图论# #生成树#
【代码详解】
#include <bits/stdc++.h>
using namespace std;const int N = 1005; // 最大节点数
const int M = N * N / 2; // 最大边数（完全图边数）// 边结构体
struct Edge
{int a, b, w; // a:起点, b:终点, w:权重// 重载小于运算符，用于按权重排序bool operator< (const Edge &t) const{return w < t.w;}
} e[M]; // 边数组int A; // 建立发电站的成本
int B; // 村庄数量
int cur; // 当前边数计数器
int ans; // 最小生成树的总成本
int cnt; // 已选择的边数（实际未使用）
int p[N]; // 并查集数组，用于记录节点的父节点/*** 并查集查找操作（带路径压缩）* @param x 要查找的节点* @return 节点x的根节点*/
int find(int x)
{if (p[x] != x){p[x] = find(p[x]); // 路径压缩}return p[x];
}int main()
{// 输入建立发电站的成本和村庄数量cin >> A >> B;// 初始化并查集，每个节点独立成集合for (int i = 0; i <= B; i++){p[i] = i;}// 添加虚拟边：每个村庄建立发电站的选项// 将发电站视为节点0，建立发电站相当于连接村庄到节点0for (int i = 1; i <= B; i++){e[++cur].a = 0; // 起点为虚拟节点0（发电站）e[cur].b = i; // 终点为村庄ie[cur].w = A; // 权重为建立发电站的成本A}// 输入村庄之间架设电线的成本for (int i = 1; i <= B; i++){for (int j = 1; j <= B; j++){int x;cin >> x;// 跳过成本为0的情况（可能表示无法连接或自身）if (x == 0){continue;}// 添加村庄之间的连接边e[++cur].a = i;e[cur].b = j;e[cur].w = x;}}// 调试输出（注释掉的代码）// for (int i=1; i<=cur; i++)// cout << e[i].a << " " << e[i].b << " " << e[i].w << endl;// 将边按成本从小到大排序（Kruskal算法的关键步骤）sort(e + 1, e + cur + 1);// 使用Kruskal算法构建最小生成树for (int i = 1; i <= cur; i++){int a = find(e[i].a); // 查找起点的根节点int b = find(e[i].b); // 查找终点的根节点int w = e[i].w; // 当前边的权重// 如果两个节点不在同一个连通分量中if (a != b){p[a] = b; // 合并两个连通分量ans += w; // 累加当前边的成本}}// 输出最小总成本cout << ans << endl;return 0;
}
【运行结果】
1 1
0
1