渝网互联重庆网站制作_建站公司专业团队_b2b_2023年时政热点事件

题目

P1195 口袋的天空 - 洛谷 | 计算机科学教育新生态

分析

：连在一起：并查集

代价最小：贪心

集合树==棉花糖数：合并（涉及代价）

从最小代价开始判断是否合并。

代价的存储用结构体。

无非是玩数据存储和数据处理

代码 

#include<bits/stdc++.h>
using namespace std;//连在一起，并查集
// 代价最小-贪心-
const int N = 1e5+10;
int p[N];
int cnt[N];
struct arr{int x, y;int l;bool operator <(const arr &W) const {return l < W.l;}
}A[N];void init() {for(int i = 1; i < N; i ++) p[i] = i;
}int find(int x) {if(p[x]!=x) p[x] = find(p[x]);return p[x];
} int main() {init();int n, m, k;cin >> n >> m >> k;int num = n-k;for(int i = 0; i < m; i ++) {int x, y, l;cin >> x >> y >> l;A[i].x = x, A[i].y = y, A[i].l = l;}sort(A,A+m);if(n<k) {puts("No Answer");}int ans = 0;for(int i = 0,j = 0; i < m && j < num; i ++) {int a = find(A[i].x), b = find(A[i].y);if(a==b) continue;j ++;p[a] = b;cnt[b] += cnt[a] + A[i].l; //ans += A[i].l;}
//	int ans = 0;for(int i = 1; i <= n; i ++) {if(find(i)==i) ans += cnt[i];}cout << ans << endl;return 0;
}

#include<bits/stdc++.h>
using namespace std;//连在一起，并查集
// 代价最小-贪心-
const int N = 1e5+10;
int p[N];
int cnt[N]; // 用不上
struct arr{int x, y;int l;bool operator <(const arr &W) const {return l < W.l;}
}A[N];void init() {for(int i = 1; i < N; i ++) p[i] = i;
}int find(int x) {if(p[x]!=x) p[x] = find(p[x]);return p[x];
} int main() {init();int n, m, k;cin >> n >> m >> k;int num = n-k;for(int i = 0; i < m; i ++) {int x, y, l;cin >> x >> y >> l;A[i].x = x, A[i].y = y, A[i].l = l;}sort(A,A+m);if(n<k) {puts("No Answer");}int ans = 0;for(int i = 0,j = 0; i < m && j < num; i ++) {int a = find(A[i].x), b = find(A[i].y);if(a==b) continue;j ++;p[a] = b;cnt[b] += A[i].l; ans += A[i].l;}
//	int ans = 0;
//	for(int i = 1; i <= n; i ++) {
//		if(find(i)==i) ans += cnt[i];
//	}cout << ans << endl;return 0;
}