hdu 3371

#include<stdio.h>

#include<stdlib.h>

#define N 501

struct node {

int x,y,dis;

}road[N*N];

int pre[N];

int find (int n ) {

return pre[n]=n==pre[n]?n:find(pre[n]);

}

int cmp(const void *a,const void *b) {

return (*(struct node *)a).dis>(*(struct node *)b).dis?1:-1;

}

int main() {

int n,m,k,t,a,b,c,cnt,sum,flag,i,j,len,f1,f2;

scanf("%d",&t);

while(t--) {

scanf("%d%d%d",&n,&m,&k);

for(i=1;i<=n;i++)

pre[i]=i;

for(i=0;i<m;i++) {

scanf("%d%d%d",&a,&b,&c);

road[i].x=a;

road[i].y=b;

road[i].dis=c;

}

sum=0;

cnt=0;

qsort(road,m,sizeof(road[0]),cmp);

while(k--) {

scanf("%d%d",&len,&a);

f1=find(a);

len--;

while(len--) {

scanf("%d",&b);

f2=find(b);

if(f1!=f2) {

cnt++;

pre[f2]=f1;

}

}

}

for(i=0;cnt<n&&i<m;i++) {

f1=find(road[i].x);

f2=find(road[i].y);

if(f1!=f2) {

cnt++;

sum+=road[i].dis;

pre[f2]=f1;

}

}

if(cnt==n-1)

printf("%d\n",sum);

else

printf("-1\n");

}

return 0;

}

巴特西

hdu 3371

最新文章

热门文章