南阳理工学院ACM多乐赛暨16级退役纪念赛　B PK吹泡泡

题目来源：http://acm.nyist.edu.cn/problem/1662

题目描述:

经历了一天的训练之后，PK准备放松一下，在草坪上吹起了泡泡。经历了PK 的一顿操作之后，天空中出现了N个泡泡，每个泡泡都有个编号。 给出了 m个关系，每个关系以u v w 的形式给出，表示编号为u的泡泡可以和编号为v的泡泡连在一起，且花费的代价为w。
这时， PK想到了一个问题：如何以最小的代价把这 n个泡泡中的一些泡泡连在一起，使得天空中出现 k个泡泡联通块？可是 PK沉浸在了泡泡的海洋无法自拔，不想思考这个问题，他希望你来替他回答。

输入描述:

第一行三个整数n，m和k(1 <= k <= n <= 1000, 1 <= m <= 500000)。表示泡泡的个数，PK 给出的关系数以及最终要形成的泡泡联通块数。
接下来的m行，每行三个数u, v, w(1 <= u, v <= n, 0 < w <= 1000000)，表示你可以把泡泡u和泡泡v连在一起，需要花费的代价为w。

输出描述:

输出一个整数，表示把这 n 个泡泡中的一些泡泡连在一起使得天空中出现 k 个泡泡联通块的最小代价。

样例输入：

4 4 2
1 2 1
2 3 4
3 4 2
1 4 5

样例输出:

3

并查集瞎搞（搞出来和kruskal差不多
初始状态下看做n个联通块,向两个不不联通的联通块添加一一条边,视作联通块的数目目-1。
对边进行行行排序后用用并查集维护联通块关系,直到只剩K个联通块。（不是加入ｋ个点break,而是当天空剩下ｋ个联通快跳出也就是在合并的时候判断。（详细看代码

参考代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<map>
#define ll long long
const int N=1e6+5;
#define inf 0x3f3f3f3f
using namespace std;
#define mem(a,b) memset(a,b,sizeof(a))
int pre[N],n,m,k,num;
struct node
{
   int u,v,w;
} mmp[500005];
bool cmp(node a,node b)
{
       return a.w<b.w;
}
void init()
{
   for(int i=1; i<=n; i++)
       pre[i]=i;
}
int Find(int x)
{
   return x==pre[x]?x:pre[x]=Find(pre[x]);
}
bool Join(int x,int y)
{
   int fx=Find(x),fy=Find(y);
   if(fx!=fy)
   {
       num--;
       pre[fy]=fx;
       return 1;
   }
   return 0;
}
int kruskal(){
   int sum=0;
   for(int i=0;i<m;i++) {
       if (Join(mmp[i].u, mmp[i].v)) {
           sum += mmp[i].w;
       }
       if (num==k)
           break;
   }
   return sum;
}
int main()
{
    //freopen("//home/nuoyanli//文档//0615//B//data//secret//3.in", "rep", stdin);
   cin>>n>>m>>k;
   num=n;
   init();
   for(int i=0; i<m; i++)
   {
       int a,b,c;
       cin>>a>>b>>c;
       mmp[i].u=a,mmp[i].v=b,mmp[i].w=c;
   }
   sort(mmp,mmp+m,cmp);
   cout<<kruskal()<<endl;
   return 0;
}
/** 4 4 2 1 2 1 2 3 4 3 4 2 1 4 5 3 4 3 2 1 2 1 2 3 2 3 4 1 2 5 3 2 1 2 1 2 3 2 3 4 1 **/