hdu3371

这题本来不想写题解的，太容易了，就赤裸裸的最小生成树，不过由于我没考虑
会有重边输入，所以我就wa了几遍，看了别人的评论后才改过ac了
细节是魔鬼吖！！！
prime算法也531ms过的，估计克鲁斯卡尔算法不优化的话会超时，毕竟是25000条边

531ms代码
#include<iostream>

int g[505][505];

int prime(int n)
{
 int min,i,j,k,sum=0;
 int lowest[505];
 int flag[505];
 lowest[1]=0;
 flag[1]=1;
 for(i=2;i<=n;i++)
 {
  lowest[i]=g[1][i];
  flag[i]=0;
 }
 k=1;
 for(i=2;i<=n;i++)
 {
  min=500001;
  for(j=2;j<=n;j++)
  {
   if(min>lowest[j]&&!flag[j]){min=lowest[j];k=j;}
  }
  if(min>1000)
   return -1;
  sum+=min;
  flag[k]=1;
  for(j=2;j<=n;j++)
  {
   if(!flag[j]&&lowest[j]>g[k][j])
    lowest[j]=g[k][j];
  }
 }
 return sum;
}

int main()
{
 int t,n,m,k,i,j,h;
 int x,y,ans,z,q;
 int a[505];
 scanf("%d",&t);
 while(t--)
 {
  scanf("%d %d %d",&n,&m,&k);
  for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
    g[i][j]=500001;
  for(i=1;i<=m;i++)
  {
   scanf("%d %d %d",&x,&y,&z);
   if(g[y][x]>z)
   g[y][x]=g[x][y]=z;
  }
  for(i=1;i<=k;i++)
  {
   scanf("%d",&q);
   for(j=1;j<=q;j++)
    scanf("%d",&a[j]);
   for(j=1;j<=q;j++)
   {
    for(h=j+1;h<=q;h++)
     g[a[j]][a[h]]=g[a[h]][a[j]]=0;
   }
  }
  ans=prime(n);
  printf("%d\n",ans);
 }
 return 0;
}

本文出自 “Qero” 博客，请务必保留此出处http://8590696.blog.51cto.com/8580696/1358894

hdu3371

原文：http://8590696.blog.51cto.com/8580696/1358894