解题报告：有n个点，然后有m条可以添加的边，然后有一个k输入，表示一开始已经有k个集合的点，每个集合的点表示现在已经是连通的了。
还是用并查集加克鲁斯卡尔。只是在输入已经连通的集合的时候，通过并查集将该集合的点标记到一起，然后剩下的就可以当成是普通的最小生成树来做了题目代码如下：
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 #include<cstdlib> 6 using namespace std; 7 8 struct node 9 { 10 int front ,rear,cost; 11 }rode[25005]; 12 int pre[505]; 13 int find(int n) 14 { 15 return pre[n] == n? n:pre[n] = find(pre[n]); 16 } 17 int cmp(const void *a,const void *b) 18 { 19 return (*(node*)a).cost <= (*(node*)b).cost? -1:1; 20 } 21 int judge(int n) 22 { 23 for(int i = 2;i <= n;++i) 24 if(find(1) != find(i)) 25 return 0; 26 return 1; 27 } 28 29 int main() 30 { 31 int T; 32 int ci,s,d; 33 scanf("%d",&T); 34 while(T--) 35 { 36 int n,m,k; 37 scanf("%d%d%d",&n,&m,&k); 38 for(int i = 1;i <= m;++i) 39 scanf("%d%d%d",&rode[i].front,&rode[i].rear,&rode[i].cost); 40 qsort(rode+1,m,sizeof(node),cmp); 41 for(int i = 1;i <= n;++i) 42 pre[i] = i; 43 while(k--) 44 { 45 scanf("%d%d",&ci,&s); 46 ci--; 47 while(ci--) 48 { 49 scanf("%d",&d); 50 pre[find(s)] = find(d); 51 } 52 } 53 int ans = 0; 54 for(int i = 1;i <= m;++i) 55 { 56 int temp1 = find(rode[i].front); 57 int temp2 = find(rode[i].rear); 58 if(temp1 != temp2) 59 { 60 ans += rode[i].cost; 61 pre[temp1] = temp2; 62 } 63 } 64 printf(judge(n)? "%d ":"-1 ",ans); 65 } 66 return 0; 67 }
不过，我过这道题的时候发现一个小问题，就是在排序的时候用sort总会T，但是发现改成qsort之后，比原来快了很多，然后就A了。经过一些测试发现，qsort在数据量比较大的时候要比sort更快，而且数据量越大，差别越大，下面再附上测试用的代码：
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<time.h> 5 using namespace std; 6 7 const int maxn = 100000; 8 9 int que[maxn]; 10 11 int cmp(const void *a,const void *b) 12 { 13 return (*(int*)a) <= (*(int*)b)? -1:1; 14 } 15 bool comp(int a,int b) 16 { 17 return a <= b; 18 } 19 int main() 20 { 21 for(int i = maxn - 1;i >=0;--i) 22 que[i] = i; 23 int s = clock(); 24 qsort(que,maxn,sizeof(int),cmp); 25 int e = clock(); 26 printf("t_qsort = %d ",e - s); 27 s = clock(); 28 sort(que,que+maxn,comp); 29 e = clock(); 30 printf("t_sort = %d ",e - s); 31 return 0; 32 }