POJ-1258 解题报告

题意简述

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

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

算法分析

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

程序样例

[c]
#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("%dn",prim(n,map));
}
return 0;
}
[/c]

One thought on “POJ-1258 解题报告

  1. 周一口 says

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

    Reply

Leave a Reply

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