比赛 防止浮躁的小练习V0.1 评测结果 AAAAAAAAAA
题目名称 口袋的天空 最终得分 100
用户昵称 ‎MistyEye 运行时间 0.013 s
代码语言 C++ 内存使用 0.47 MiB
提交时间 2016-10-07 16:51:00
显示代码纯文本
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1005, maxm = 10005;
int N, M, K;
int a[maxm], b[maxm], d[maxm], lis[maxm];
int f[maxn];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
bool cmp(const int& x, const int& y) { return d[x]<d[y]; }
int main(){
    freopen("cotton.in","r",stdin); freopen("cotton.out","w",stdout);
	scanf("%d%d%d", &N, &M, &K);
	for(int i=1; i<=M; ++i) {
		scanf("%d%d%d", a+i, b+i, d+i);
		lis[i] = i;
	}
	sort(lis+1, lis+M+1, cmp);
#define tot N-K
	int cnt = 0, ans = 0;
	for(int i=1; i<=N; ++i) f[i] = i;
	for(int i=1; i<=M; ++i){
		int e = lis[i];
		int fa = find(a[e]), fb = find(b[e]);
		if(fa==fb) continue;
		f[fb] = fa;
		ans += d[e];
		if(++cnt==tot) break;
	}
	if(cnt<tot) printf("No Answer\n");
	else printf("%d\n", ans);
	return 0;
}