并查集

https://www.luogu.com.cn/problem/P1195

#include<cstdio>
#include<algorithm>
using namespace std;
const int n = 1001;
const int m = 10001;
int ans = 0;
struct Edge
{
   int u,v,w;
};
Edge E[m];
int  father[n];
void Init_father()
{
   for(int i=1;i<=n;i++)
   {
       father[i]=i;
   }
}
bool comp(Edge lhs,Edge rhs)
{
   if(lhs.w<rhs.w)
       return true;
   else
       return false;
}
int find(int x)
{
   while(x != father[x])
   {
       x = father[x];
   }
   return x;
}
int main()
{
   int N,M,K;//N为云朵数目，M为关系数目，K为棉花糖数目
   scanf("%d%d%d",&N,&M,&K);
   for(int i=1;i<=M;i++)
   {
       scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].w);
   }
   Init_father();
   sort(E+1,E+1+M,comp);
   for(int i=1;i<=M;i++)
   {
       int countaaa = 0;
       //遍历每一条边
       int father_u=find(E[i].u);
       int father_v=find(E[i].v);
       if(father_u != father_v)
       {
           //Union操作
           father[father_u]=father_v;
           ans = ans + E[i].w;//不在一个集合中则加入这条边且权值增加
       }
      //统计此时有几个集合了
      for(int j=1;j<=N;j++)
      {
          if(father[j] == j)
          {
              countaaa++;
          }
      }
      if(countaaa == K)
      {
          //达到了K个集合
          printf("%d",ans);
          return 0;//达到K个集合则停止循环,注意要使用return语句而不是break，使用break之后后面NA也会被输出
      }
   }
   //循环完毕都没有达到K个集合
   printf("No Answer");
}