题目大意：给定平面上N个城市的位置，计算连接这N个城市所需线路长度总和的最小值。
MST问题。
以下是我的代码，采用Prim算法求解：
#include<cstdio>
#include<cmath>
using namespace std;
const int kMaxn(107);
const int kInf(0x7f7f7f7f);
int n;
double x[kMaxn],y[kMaxn],g[kMaxn][kMaxn];
double mst,lowcost[kMaxn];
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
int T(0);
while(scanf("%d",&n)==1 && n)
{
for(int i=1;i<=n;i++)
scanf("%lf%lf",&x[i],&y[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
mst=.0;
for(int i=1;i<=n;i++)
lowcost[i]=g[1][i];
lowcost[1]=-1;
for(int i=1;i<n;i++)
{
int pos(-1);
double minvalue(kInf+.0);
for(int j=1;j<=n;j++)
if(lowcost[j]!=-1 && minvalue>lowcost[j])
{
pos=j;
minvalue=lowcost[j];
}
if(pos!=-1)
{
mst+=minvalue;
lowcost[pos]=-1;
for(int j=1;j<=n;j++)
if(lowcost[j]!=-1 && lowcost[j]>g[pos][j])
lowcost[j]=g[pos][j];
}
}
T++;
if(T!=1)
printf("\n");
printf("Case #%d:\n",T);
printf("The minimal distance is: %.2f\n",mst);
}
return 0;
}
posted on 2011-05-27 16:05
lee1r 阅读(272)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：图论