嗯...

 

题目链接：https://www.luogu.org/problemnew/show/P1195

 

思路：

首先可以判断这道题是用最小生成树来做的，然后在将其合并时用ans记录一下它的总消耗，然后用一个sum记录一下一共将几块云朵合并在了一起....

每合并完一次，都要进行判断（k是否等于n-sum，即是否已经合并成了k块棉花糖），如果已符合题意，则return即可。这是这道题的一个重点，否则会继续跑下去....

 

AC代码：

1 #include
      
        2 #include
       
         3 #include
        
          4  5 using namespace std; 6  7 int f[10005], sum, ans; 8  9 struct node{10     int x, y, l;11 } a[10005];12 13 inline int cmp(node i, node j){14     return i.l < j.l;15 }16 17 inline int find(int x){18     if(f[x] != x)19         f[x] = find(f[x]);20     return f[x];21 }22 23 int main(){24     int n, m, k;25     scanf("%d%d%d", &n, &m, &k);26     for(int i = 1; i <= m; i++)27         scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].l);28     for(int i = 1; i <= n; i++)29         f[i] = i;30     sort(a+1, a+m+1, cmp);31     for(int i = 1; i <= m; i++){32         int r1 = find(a[i].x);33         int r2 = find(a[i].y);34         if(r1 != r2){35             f[r1] = r2;36             sum++;37             ans += a[i].l;38         }39         if(k == n - sum){ //是否已经合并成k块棉花糖 40             printf("%d", ans);41             return 0;42         }43     }44     printf("No Answer");45     return 0;46 }