[infobox title="https://www.luogu.org/problem/show?pid=1195"]题目背景

小杉坐在教室里，透过口袋一样的窗户看口袋一样的天空。

有很多云飘在那里，看起来很漂亮，小杉想摘下那样美的几朵云，做成棉花糖。

题目描述

给你云朵的个数N，再给你M个关系，表示哪些云朵可以连在一起。

现在小杉要把所有云朵连成K个棉花糖，一个棉花糖最少要用掉一朵云，小杉想知道他怎么连，花费的代价最小。[/infobox]

解法...
没有解法..直接把最后K个结果忽略就好了...
[code lang="cpp"]#include<cstdio>
#include<iostream>
#include<algorithm>
#define MAXN 5050
#define MAXM 200050
using namespace std;
struct edge{
int x, y, d;
}e[MAXM];
int f[MAXN];
int n, m, k;

int find(int i){
if (i != f[i]) f[i] = find(f[i]);
return f[i];
}

bool cmp(edge a, edge b){
return a.d < b.d;
}

int main(){
int ans = 0;
scanf("%d%d%d", &n, &m, &k);
for (int i = 0; i < m; i++) scanf("%d%d%d", &e[i].x, &e[i].y, &e[i].d);
for (int i = 0; i < n; i++) f[i] = i;
sort(e, e + m, cmp);
int cnt = 0;
for (int i = 0; i < m; i++){
int af = find(e[i].x), bf = find(e[i].y);
if (af != bf){
f[bf] = af;
ans += e[i].d;
cnt++;
if (cnt == n - k) break;
}
}
printf("%d", ans);
}[/code]