P1194 买礼物
普及的题目,而且一眼就能看出该用什么做法。
我主要是决定这道题建图的思想值得借鉴,每样东西原本的价格是a,所以新建一个节点0, 0向i连边,边权为a,这样一共就有b + 1个点,跑kruskal的时候记录加入的边数,=b时就break。
#include <bits/stdc++.h>
using namespace std;
int a, b, fa[510], cnt;
struct edge {
int u, v, w;
bool operator < (const edge &a) const {
return w < a.w;
}
}e[250100];
int getfa(int x) {return fa[x] == x ? x : fa[x] = getfa(fa[x]);}
int main() {
cin >> a >> b;
cnt = 0;
for (int i = 0; i <= b; i ++) fa[i] = i;
for (int i = 1; i <= b; i ++) {
e[++ cnt] = (edge) {0, i, a};
for (int j = 1; j <= b; j ++) {
int x; cin >> x;
if (i < j && x != 0)
e[++ cnt] = (edge) {i, j, x};
}
}
int t = 0, ans = 0;
sort(e + 1, e + cnt + 1);
for (int i = 1; i <= cnt; i ++) {
int x = e[i].u, y = e[i].v, z = e[i].w;
int fx = getfa(x), fy = getfa(y);
if (fx != fy) {
fa[fx] = fy;
t ++;
ans += z;
}
if (t == b) break;
}
printf("%d\n", ans);
return 0;
}