D

- 题目大意

    某地发洪水，导致某些城市被淹而消失，现在想把剩下的零散的城市通过修路连接起来，已知现在有部分城市是连通的。可选择修的路有m条，城市总共有n个，给出了m条路的起点终点和修路花费，问最少可花多少钱能保证所有的城市连通。

- 解题思路

   可以用kruskal。把边权排序然后并查集添加边即可。

- 代码

#include<algorithm>
#include<cstdio>
using namespace std;
int fa[505];

struct Edge {
	int u, v, w;
	bool operator<(const Edge &rhs)const {
		return w < rhs.w;
	}
}e[25005];
void init(int n)
{
	for (int i = 1; i <= n; i++)
		fa[i] = i;
}

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

bool Union(int x, int y)
{
	int fx = find(x), fy = find(y);
	if (fx == fy)
		return false;
	else
	{
		fa[fx] = fy;
		return true;
	}
}

void kruskal(int m,int k)
{
	int sum = 0;
	sort(e, e + m);
	for (int i = 0; i < m; i++)
	{
		int u = e[i].u, v = e[i].v, w = e[i].w;
		if (Union(u, v))
		{
			sum += w;
			k--;
		}
	}
	if (!k)
		printf("%d
", sum);
	else
	{
		printf("-1
");
	}
}
int main()
{
	int n,m,t,p,q,c,k,tmp;
	scanf_s("%d",&t);
	while (t--)
	{
		scanf_s("%d%d%d",&n,&m,&k);
		init(n);
		for (int i = 0; i < m; i++)
			scanf_s("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
		tmp = n-1;
		for (int j = 0; j < k; j++)
		{
			scanf_s("%d%d",&p,&q);
			while (--p)
			{
				scanf_s("%d", &c);
				if (Union(q,c))
				{
					tmp--;
				}
		    }
		}
		kruskal(m, tmp);
		
	}
	return 0;
}