Dayi Lin, Ph.D.

Principal Researcher, AI & Software Engineering

POJ-1258 解题报告

POJ

题意简述

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

注意:输入数据有多组,用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;
}

1 Comments on “POJ-1258 解题报告”

  1. 刚刚下了wordpress….不太会玩诶….那个php用什么版本的?mysql也是,然后有配置的教程不linda~

Leave a Reply

Your email address will not be published. Required fields are marked *