hdu1233+1863

第一次做最小生成树，由于点只有100个，故采用普利姆算法会合理一点，两题都差不多
就是1863的每次读入点后检验一下最小权值是否小于0就ok了
1863的0ms代码如下（1233的就改一改就好了）
#include<iostream>
#include<string>

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

void memset(int n)
{
 int i;
 flag[1]=true;
 for(i=2;i<=n;i++)
 {
  lowest[i]=g[1][i];
  closest[i]=1;
  flag[i]=false;
 }
}

int prime(int n)
{
 int i,j,k,sum=0;

 for(i=2;i<=n;i++)
 {
  int min=2147483647;k=1;
  for(j=2;j<=n;j++)
   if(lowest[j]<min&&(!flag[j])) {min=lowest[j];k=j;}
  flag[k]=true;
  sum+=min;
  if(sum<0)
  {
   return -2;
  }
  for(j=2;j<=n;j++)
  {
   if(g[k][j]<lowest[j]&&(!flag[j]))
   {
    lowest[j]=g[k][j];
    closest[k]=j;
   }
  }
 }
 return sum; 
}

int main()
{
 int i,n,j,x,y,d,ans,m;
 while(scanf("%d %d",&m,&n)&&m)
 {
  for(i=1;i<=n;i++)
  {
   for(j=1;j<=n;j++)
   {
    g[i][j]=2147483647;
   }
  }
  for(i=1;i<=m;i++)
  {
   scanf("%d %d %d",&x,&y,&d);
   g[x][y]=d;
   g[y][x]=d;
  }
  memset(n);
  ans=prime(n);
  if(ans<0)
   printf("?\n");
  else
   printf("%d\n",ans);
 }

    return 0;
}

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

hdu1233+1863

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