HDU - 3371 题意：建最小生成树不过已经有一些集合中的点都建好了。思路：最初以为每个集合中的点都需要相互连通一下，不过由于只最小生成树所以只需都于集合中的第一个点相连为0即可
Connect the Cities
#include<bits/stdc++.h>
using namespace std;
#define maxn 55555
struct node
{
int x,y,z;
} edge[maxn];
int n,m,k,t,u,v,w,s,cnt;
int fa[maxn],ans,b[maxn];
int fond(int x)
{
return x==fa[x]?x:fa[x]=fond(fa[x]);
}
bool cmp(node a,node b)
{
return a.z<b.z;
}
bool kru()
{
for(int i=1; i<=n; i++)
fa[i]=i;
sort(edge,edge+cnt,cmp);
for(int i=0; i<cnt; i++)
{
int xx=fond(edge[i].x);
int yy=fond(edge[i].y);
if(xx==yy)
continue;
fa[xx]=yy;
ans+=edge[i].z;
n--;
if(n==1)
return true;
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin>>t;
while(t--)
{
ans=0;
cin>>n>>m>>k;
for(int i=0; i<m; i++)
{
cin>>u>>v>>w;
edge[i].x=u;
edge[i].y=v;
edge[i].z=w;
}
cnt=m;
while(k--)
{
cin>>s;
for(int i=0; i<s; i++)
{
cin>>b[i];
if(i>0)
{
edge[cnt].x=b[0];
edge[cnt].y=b[i];
edge[cnt++].z=0;
}
}
}
if(kru())
cout<<ans<<endl;
else
cout<<-1<<endl;
}
return 0;
}
