10分求助
查看原帖
10分求助
186546
lwyznoip楼主2024/7/22 19:46
#include <bits/stdc++.h>
#define int long long

using namespace std;

int fa[200005];
int n, m, k;
struct node{
	
	int u, v, sum;
	
} e[200005];

int find (int x){
	
	if (fa[x] == x) return x;
	else return fa[x] = find (fa[x]);
	
}

map <int, int> siz;

void hebing (int x, int y){
	
	x = find (x);
	y = find (y);
	
	if (x == y) return;
	
	if (siz[x] > siz[y]) swap (x, y);
	fa[x] = y;
	siz [y] += siz[x];
	
}

bool cmp (node x, node y){
	
	return x.sum < y.sum;
	
}

int kls (){
	
	int l, r, t = 0, ans = 0;
	
	for (int i = 1; i <= m; i ++){
		
		l = find (e[i].u);
		r = find (e[i].v);
		
		if (l != r){
			
			fa[l] = r;
			ans += e[i].sum;
			t ++;
			
		}
		
	}
	
	if (t == n - k) return ans;
	else return -114514;
	
}

signed main(){
	
	cin >> n >> m >> k;
	
	for (int i = 1; i <= n; i ++){
		
		fa[i] = i;
		
	}
	
	for (int i = 1; i <= m; i ++){
		
		int x, y, z;
		cin >> x >> y >> z;
		
		e[i].u = x;
		e[i].v = y;
		e[i].sum = z;
		
	}
	
	sort (e + 1, e + m + 1, cmp);
	
	int h = kls ();
	
	if (h != -114514){
		
		cout << h;
		return 0;
		
	}
	
	cout << "No Answer";
	
	return 0;
	
}
2024/7/22 19:46
加载中...