1195口袋的天空——并查集+贪心——洛谷

题目

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;
}