洛谷 P1195 口袋的天空

Description

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

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

Input

• 第一行有三个数N,M,K(1≤N≤1000,1≤M≤10000,1≤K≤10)

  接下来M个数每行三个数X,Y,L，表示X云和Y云可以通过L的代价连在一起。(1≤X,Y≤N,0≤L<10000)

Output

• 对每组数据输出一行，仅有一个整数，表示最小的代价。

  如果怎么连都连不出K个棉花糖，请输出'No Answer'。

Sample Input

3 1 2

1 2 1

Sample Output

1

题解：

• 一道裸奔的最小生成树居然是绿题！?
• 这题考语文，要k个棉花糖其实就是k个点联通的最小代价

#include 
    
     #include 
     
      #include 
      
       #define N 10005using namespace std;struct E {int u, v, w;} e[N];int n, m, k, num, cnt, ans;int h[N], fat[N];bool cmp(E x, E y) {    return x.w < y.w;}int getFat(int x){    if(x == fat[x]) return x;    else return fat[x] = getFat(fat[x]);}void minTree(){    for(int i = 1; i <= n; i++) fat[i] = i;    sort(e + 1, e + 1 + m, cmp);    for(int i = 1; i <= m; i++)    {        if(getFat(e[i].u) != getFat(e[i].v))            fat[getFat(e[i].u)] = getFat(e[i].v),            cnt++, ans += e[i].w;        if(cnt == n - k) break;    }}int main(){    cin >> n >> m >> k;    for(int i = 1; i <= m; i++)        cin >> e[i].u >> e[i].v >> e[i].w;    minTree();    cout << ans;    return 0;}