数据结构 || 图论 || 并查集+最小生成树（kruskal）

Connect the Cities

Problem Description
In 2100, since the sea level rise, most of the cities disappear. Though some survived cities are still connected with others, but most of them become disconnected. The government wants to build some roads to connect all of these cities again, but they don’t want to take too much money.  
Input
The first line contains the number of test cases.
Each test case starts with three integers: n, m and k. n (3 <= n <=500) stands for the number of survived cities, m (0 <= m <= 25000) stands for the number of roads you can choose to connect the cities and k (0 <= k <= 100) stands for the number of still connected cities.
To make it easy, the cities are signed from 1 to n.
Then follow m lines, each contains three integers p, q and c (0 <= c <= 1000), means it takes c to connect p and q.
Then follow k lines, each line starts with an integer t (2 <= t <= n) stands for the number of this connected cities. Then t integers follow stands for the id of these cities.
Output
For each case, output the least money you need to take, if it’s impossible, just output -1.
Sample Input
1 6 4 3 1 4 2 2 6 1 2 3 5 3 4 33 2 1 2 2 1 3 3 4 5 6
Sample Output

1

存在连通和不连通的城市，求造路连通所有城市花费的最少金额

Kruskal：按照边的权值从小到大判断，若不产生圈（边两端的点不是连通的/不属于同一个集合），就把边加入到生成树中，最后能得到最小生成树

#include<stdio.h>#include<memory.h>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
int n,m,k;
int pre[505];
int ans;
struct Edge{
	int x;
	int y;
	int c;
};
Edge e[25005];

int en;//！！！所有点连通，只需要与n-1条边 

int find(int x){    
    if(pre[x]==x)return x;    
    else{    
        int r=find(pre[x]);    
        pre[x]=r;           
        return pre[x];    
    }    

}
int join(int x,int y){  

        int rx=find(x);  
        int ry=find(y);  
        if(rx!=ry){ 
        	en--;//成功加入一条边，则更新en 
           pre[ry]=rx;
           return 1;
        }
        return 0;
}
bool cmp(Edge a,Edge b){
	return a.c<b.c;
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		scanf("%d%d%d",&n,&m,&k);
		for(int i=1;i<=n;i++){
			pre[i]=i;
		}
		en=n-1;
		for(int i=1;i<=m;i++){
			scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].c);
		}

		sort(e+1,e+m+1,cmp);//边按权值排序，以便后续贪心选择 

		int t,a,b;
		for(int i=1;i<=k;i++){
			scanf("%d",&t);
			scanf("%d",&a);
			for(int j=2;j<=t;j++){
				scanf("%d",&b);
				join(a,b);
			}
		}
		ans=0;
		for(int i=1;i<=m;i++){
			if(join(e[i].x,e[i].y)==1){
				ans+=e[i].c;//对符合条件的边进行贪心选择 
				if(en==0)break;//已经有n-1条边，则所有点已经连通，不用再进行后续判断（如果继续会超时） 
			}
		}
		if(en)printf("-1\n");
		else printf("%d\n",ans);
	}

	return 0;
}