POJ-1258 解题报告

题意简述

农夫需要将他的农场与其他农场联网，每两个农场联网的代价已知，求使所有农场互相联通的最小代价。

注意：输入数据有多组，用while(scanf("%d",&n)!=EOF)判断是否完成输入。

算法分析

典型的最小生成树，使用Kruskal算法或Prim算法都能解决。我使用的是Prim算法。

程序样例

#include<stdio.h>
#define MaxI 999999

int prim(int n, int map[][100])
{
  int d[100],used[100]={0},m,ans=0,min,mini,i;
  for(i=1;i<n;i++)
  d[i]=MaxI;
  d[0]=0;
  for(m=0;m<n;m++)
  {
    min=MaxI;
    for(i=0;i<n;i++)
      if ((!used[i])&&(d[i]<min))
      {
        mini=i;
        min=d[i];
      }
    used[mini]=1;
    ans=ans+min;
    for(i=0;i<n;i++)
      if ((!used[i])&&(map[mini][i]<d[i]))
        d[i]=map[mini][i];
  }
  return ans;
}

int main()
{
  int n,i,j,map[100][100];
  while(scanf("%d",&n)!=EOF)
  {
    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
        scanf("%d",&map[i][j]);
        printf("%d\n",prim(n,map));
  }
  return 0;
}