hdu 3371 Connect the Cities

本文主要是介绍hdu 3371 Connect the Cities，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

简单题型：把有联系的城市直接合并，注意的是要记录合并的总数；

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"algorithm"
using namespace std;
int pre[500];
int find(int k)
{
 if(k!=pre[k])
  pre[k]=find(pre[k]);
 return pre[k];
}
struct point
{
 int x,y,z;
}a[25002];
int cmp(point a,point b)
{
 return a.z<b.z;
}
int main()
{
 int m,n,i,k,h,b,c,xx,yy,d,t;
 scanf("%d",&h);
 while(h--)
 {
  t=0;
  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[i].x,&a[i].y,&a[i].z);
  }
  while(k--)
  {
   scanf("%d",&b);
   scanf("%d",&c);
   for(i=0;i<b-1;i++)
   {
    scanf("%d",&d);
    xx=find(c);
    yy=find(d);
    if(xx!=yy)
    {
     pre[yy]=xx;
     t++;
    }
   }
  }
  sort(a,a+m,cmp);
  int sum=0;
  for(i=0;i<m;i++)
  {
   xx=find(a[i].x);
   yy=find(a[i].y);
    if(xx!=yy)
    {
     pre[yy]=xx;
     sum+=a[i].z;
     t++;
    }
  }
  if(t==n-1)
      printf("%d\n",sum);
  else
   printf("-1\n");
 }
 return 0;
}

这篇关于hdu 3371 Connect the Cities的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---