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

这题本质就是简单的Kruskal,而关键在于有n个点需要对这n个点之间进行连接最后变成k个团注意1个点也可以算作一个团接下来看看n个点变成k个团需要进行几次边的连接先说答案这是固定的一共需要n-k次连接即n-k条边我们知道连接n个点不成环需要n-1条边这时后这n个点就变成1个团那同理现在是连接以后就剩k个团是不是需要n-k条边。所以只需要把原来最小生成树模版的countn-1改成countn-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; t1getf(v); t2getf(u); if(t1!t2){ f[t2]t1; return 1; } return 0; } int main() { scanf(%d %d %d,n,m,k); for(int i1;in;i){ f[i]i; } if(nk){ printf(No Answer); return 0; } if(nk){ printf(0); return 0; } int a,b; for(int i1;im;i){ scanf(%d %d %d,a,b,L); e[i].ua; e[i].vb; e[i].wL; } qsort(e1,m,sizeof(edge),compare); int count0,sum0; for(int i1;im;i){ if(merge(e[i].u,e[i].v)){ count; sume[i].w; } if(countn-k){ break; } } if(countn-k){ printf(%d,sum); }else { printf(No Answer); } return 0; }