洛谷P1195（最小生成树+连通块）；

这题本质就是简单的Kruskal,而关键在于有n个点，需要对这n个点之间进行连接，最后变成k个团（注意1个点也可以算作一个团）；

接下来看看n个点变成k个团需要进行几次边的连接；先说答案这是固定的一共需要n-k次连接，即n-k条边，我们知道连接n个点不成环需要n-1条边，这时后这n个点就变成1个团，那同理，现在是连接以后就剩k个团，是不是需要n-k条边。所以只需要把原来最小生成树模版的count==n-1改成count==n-k即可，下面上代码。

#include <stdio.h> #include <stdlib.h> #include <string.h> typedef struct edge { int u; int v; int w; }edge; edge e[10005]; int f[1005]; int n,m,k,L; int compare(const void *a,const void *b){ edge *q1=(edge *)a; edge *q2=(edge *)b; return q1->w-q2->w; } int getf(int v){ if(f[v]==v){ return v; }else { f[v]=getf(f[v]); return f[v]; } } int merge(int v,int u){ int t1,t2; t1=getf(v); t2=getf(u); if(t1!=t2){ f[t2]=t1; return 1; } return 0; } int main() { scanf("%d %d %d",&n,&m,&k); for(int i=1;i<=n;i++){ f[i]=i; } if(n<k){ printf("No Answer"); return 0; } if(n==k){ printf("0"); return 0; } int a,b; for(int i=1;i<=m;i++){ scanf("%d %d %d",&a,&b,&L); e[i].u=a; e[i].v=b; e[i].w=L; } qsort(e+1,m,sizeof(edge),compare); int count=0,sum=0; for(int i=1;i<=m;i++){ if(merge(e[i].u,e[i].v)){ count++; sum+=e[i].w; } if(count==n-k){ break; } } if(count==n-k){ printf("%d",sum); }else { printf("No Answer"); } return 0; }