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 ",sum);
  else
  printf("-1 ");
  }
  return 0;
   }
原文地址:https://www.cnblogs.com/thefirstfeeling/p/4410955.html