题目网址：http://acm.hdu.edu.cn/showproblem.php?pid=3371
思路：
这道题很明显是一道最小生成树的题目，有点意思的是，它事先已经让几个点联通了。正是因为它先联通了几个点，所以为了判断连通性 很容易想到用并查集+kruskal。
不过要注意 这题有一个坑点，就是边数很多 上限是25000，排序的话可能就超时了。而点数则比较少 上限是500，所以很多人选择用Prim做。但我个人觉得这样连通性不好判断。其实边数多没关系，我们只要去重就好啦，用邻接矩阵存下两点间的最小权重 再排序即可，这样就不会超时啦~
代码：
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int inf=1e5;
struct node{
int v,u,w;
bool operator <(const node &x) const{
return w<x.w;
}
};
int pre[];
int mp[][];
int n,m,k;
int cnt;
vector<node>v;
void init(){
for(int i=;i<=n;i++){
pre[i]=i;
for (int j=; j<=n; j++) {
mp[i][j]=inf;
}
}
}
int query(int x){
int r=x;
while (pre[x]!=x) {
x=pre[x];
}
pre[r]=x;
return x;
}
bool join(int x,int y){
int fx=query(x);
int fy=query(y);
if(fx!=fy){
pre[fx]=fy;
return true;
}
return false;
}
int kruskal(){
int res=;
for(int i=;i<v.size();i++){
if(join(v[i].v, v[i].u)){
res+=v[i].w;
}
}
return res;
}
int main(){
int t;
int res;
scanf("%d",&t);
while (t--) {
cnt=;
v.clear();
scanf("%d%d%d",&n,&m,&k);
init();
for (int i=; i<m; i++) {
int v,u,w;
scanf("%d%d%d",&v,&u,&w);
mp[v][u]=min(mp[v][u],w);//保留最小权重
}
for (int i=; i<k; i++) {
int num,a,b;
scanf("%d",&num);
if(num) scanf("%d",&a);
for (int j=; j<num; j++) {
scanf("%d",&b);
join(a, b);
}
}
for (int i=; i<=n; i++) {
for (int j=; j<=n; j++) {
if(mp[i][j]==inf || i==j) continue;
v.push_back({i,j,mp[i][j]});//重新导入边，去掉了重复部分
}
}
sort(v.begin(), v.end());
res=kruskal();
for (int i=; i<=n; i++) {
if(pre[i]==i) cnt++;//算连通块个数
}
if(cnt==) printf("%d\n",res);
else printf("-1\n");
}
}