MST問(wèn)題。
以下是我的代碼：
#include<cstdio>
#include<cmath>
using namespace std;
const int kMaxn(107);
int n;
double x[kMaxn],y[kMaxn],z[kMaxn],r[kMaxn];
double g[kMaxn][kMaxn];
double mst,lowcost[kMaxn];
bool visited[kMaxn];
double distance(int a,int b)
{
return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b])+(z[a]-z[b])*(z[a]-z[b]));
}
void Prim()
{
mst=.0;
for(int i=1;i<=n;i++)
{
lowcost[i]=g[1][i];
visited[i]=false;
}
visited[1]=true;
for(int i=1;i<n;i++)
{
int v(-1);
double w(0x7f7f7f7f+.0);
for(int j=1;j<=n;j++)
if(!visited[j] && w>lowcost[j])
{
v=j;
w=lowcost[j];
}
if(v!=-1)
{
mst+=w;
visited[v]=true;
for(int j=1;j<=n;j++)
if(!visited[j] && lowcost[j]>g[v][j])
lowcost[j]=g[v][j];
}
}
}
int main()
{
/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
//*/
while(scanf("%d",&n)==1 && n)
{
for(int i=1;i<=n;i++)
{
scanf("%lf%lf%lf%lf",&x[i],&y[i],&z[i],&r[i]);
for(int j=1;j<i;j++)
{
double t(distance(i,j));
if(t>r[i]+r[j])
g[i][j]=g[j][i]=t-r[i]-r[j];
else
g[i][j]=g[j][i]=.0;
}
}
Prim();
printf("%.3f\n",mst);
}
return 0;
}
posted on 2011-07-31 09:46
lee1r 閱讀(211)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論