此题为最小生成树的基础题，一开始用Prim算法发现超时，当时想的是把已联通的城市当作一个城市，但发现用了太多的时间去处理。最后发现适合用kruskal求解，利用并查集的思想，对于n个点，全部连通需要ee=n-1条边，对于那些已联通的点，输入时进行处理，把他们并起来，使得在使用kruskal算法进行处理之前，那些已联通的点可视为一个点。同时，每次处理了一条边，ee--。最后，当ee==0时，得到解，否则无解。
	还需要注意的是，利用上述的解法，一直超时。最后才知道，排序时需要用快排，最后才勉强过了。![在这里插入图片描述](https://img-blog.csdnimg.cn/20190714093155682.PNG)

#include <cstdio>//kruskal,部分联通
#include <algorithm>
using namespace std;
int n,m,k,ee,ans;
struct node
{
    int s,e,w;
};
node edge[25005];
int pre[505];
int fin(int x)
{
    int r=x;
    while(r!=pre[r])
        r=pre[r];
    int i,j;
    i=x;
    while(i!=r)
    {
        j=pre[i];
        pre[i]=r;
        i=j;
    }
    return r;
}
/*bool cmp(node a,node b)
{
    return a.w<b.w;
}*/
int cmp(const void *a,const void *b){
	return ((node *)a)->w - ((node *)b)->w;
}
void kruskal()
{
    int f=0;
    for(int i=1;i<=m;i++)
    {
        int a=fin(edge[i].s);
        int b=fin(edge[i].e);
        if(a!=b)
        {
            ans+=edge[i].w;
            pre[b]=a;
            ee--;
        }
        if(ee==0)
        {
            f=1;
            printf("%d\n",ans);
            break;
        }
    }
    if(f==0)
        printf("-1\n");
}
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;
        //memset(edge,0,sizeof(edge));
        int p,q,c;
        ee=n-1;
        for(int i=1;i<=m;i++)
            scanf("%d%d%d",&edge[i].s,&edge[i].e,&edge[i].w);
        int x;
        for(int i=1;i<=k;i++)
        {
            scanf("%d",&x);
            scanf("%d",&p);
            c=fin(p);//已联通的城市取公共的父亲，则只需要连接其中一个点
            for(int j=1;j<x;j++)
            {
                scanf("%d",&p);
                q=fin(p);
                if(q!=c)
                {
                    ee--;
                    pre[q]=c;
                }
            }
        }
        //sort(edge+1,edge+1+m,cmp);
        qsort(edge+1,m,sizeof(node),cmp);
        ans=0;
        kruskal();
    }
    return 0;
}