題目大意：給定平面上N個(gè)城市的位置，計(jì)算連接這N個(gè)城市所需線路長(zhǎng)度總和的最小值。
MST問(wèn)題。
以下是我的代碼，采用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)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論