hdu1879

又一赤裸裸最小生成树，普利姆过了，不过时间复杂度感觉没比库鲁斯卡尔
好多少，也许库鲁斯卡尔会好一点
243ms代码

#include<iostream>

int g[105][105];
int lowest[105];
int flag[105];

int prime(int n)
{
 int i,j,k,min,sum=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=2147483647;
  for(j=2;j<=n;j++)
  {
   if(min>lowest[j]&&(!flag[j]))
   {
    min=lowest[j];
    k=j;
   }
  }
  sum+=min;
  flag[k]=1;
  for(j=2;j<=n;j++)
  {
   if(lowest[j]>g[k][j]&&(!flag[j]))
    lowest[j]=g[k][j];
  }
 }
 return sum;
}

int main()
{
 int n,i,a,b,z,f,ans;
 while(scanf("%d",&n)&&n)
 {
  for(i=1;i<=((n-1)*n)/2;i++)
  {
   scanf("%d %d %d %d",&a,&b,&z,&f);
   if(f) z=0;
   g[a][b]=g[b][a]=z;
  }
  ans=prime(n);
  printf("%d\n",ans);
 }
 return 0;
}

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

hdu1879

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