c/c++语言开发共享洛谷 P1195 口袋的天空

题目

p1195 口袋的天空

思路

并查集，一开始有$n$个连通块（棉花糖），因为要将所有的云连成$k$个棉花糖，我们按两朵云连成一个棉花糖的代价从小到大排序，然后按顺序判断每两朵云是否在同一连通块内，如果不在就连起来连通块数量减一直到连通块数量为$k$

$code$

#include<iostream> #include<cstring> #include<string> #include<cstdio> #include<algorithm> #define maxn 1001 using namespace std; int n,m,k; int fa[maxn],r[maxn]; struct info{     int u,v,w; }a[maxn*10]; bool cmp(info x,info y){     return x.w<y.w; } int find(int x){     return fa[x]==x?x:fa[x]=find(fa[x]); } void union(int x,int y){     int rootx=find(x),rooty=find(y);     if(rootx==rooty) return;     if(r[rootx]>r[rooty]) fa[rooty]=rootx;     else if(r[rooty]>r[rootx]) fa[rootx]=rooty;     else{         fa[rootx]=rooty;         r[rooty]++;     } } inline void read(int &t){     int x=0;bool f=0;char c=getchar();     while(c<'0'||c>'9'){if(c=='-')f=!f;c=getchar();}     while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}     t=f?-x:x; }  int main(){     read(n),read(m),read(k);     for(int i=1;i<=m;++i) read(a[i].u),read(a[i].v),read(a[i].w);     for(int i=1;i<=n;++i) fa[i]=i;     sort(a+1,a+m+1,cmp);     int ub=n,ans=0;     for(int i=1;i<=m;++i){         if(find(a[i].u)!=find(a[i].v)){             union(a[i].u,a[i].v);             ub--;             ans+=a[i].w;             if(ub==k){                 printf("%dn",ans);                 return 0;             }         }     }     puts("no answer");     return 0; }