这个题首先要把输入的坐标转化成邻接矩阵的形式。之后再利用邻接矩阵使用普里姆算法计算最小生成树。并对其中的边进行排序。找出减去S个较大的后最大的那一个。因为较大的那几个可以用卫星传输
#include<iostream>
#include<cmath>
#include<algorithm>
#include<stdio.h>
using namespace std;
typedef struct
{
double x;
double y;
}point;
point array[505];
double len[505][505];
double kk[505],next[505];
double re[505];
int sa,num;
double dis(point first,point second)
{
return sqrt((first.x-second.x)*(first.x-second.x)+(first.y-second.y)*(first.y-second.y));
}
void prim(int n)
{
int i,j;
//////////读入数据完毕。开始构建邻接矩阵
for(i=0;i<num;i++)
{
for(j=0;j<num;j++)
{
len[i][j]=15000000;
}
}
for(i=0;i<num;i++)
{
for(j=0;j<num;j++)
{
if(i!=j)
len[i][j]=dis(array[i],array[j]);
}
}
for(i=0;i<num;i++)
{
kk[i]=len[0][i];
next[i]=0;
}
/////////邻接矩阵构建完毕
int count=0;i=0;
while(count<num-1)
{
if(next[i]!=-1)
{
for(j=0;j<num;j++)
{
if(i!=j&&next[j]!=-1)
{
if(len[i][j]<kk[j])
{
kk[j]=len[i][j];
next[j]=i;
}
}
}
next[i]=-1;
double max=999999999;int k;
for(j=0;j<num;j++)
{
if(kk[j]<max&&next[j]!=-1)
{
k=j;
max=kk[j];
}
}
re[count]=max;
i=k;
count++;
}
}
}
int main()
{
int n;
cin>>n;
int i;
while(n--)
{
cin>>sa>>num;
for( i=0;i<num;i++)
{
scanf("%lf%lf",&array[i].x,&array[i].y);
}
prim(0);
sort(re,re+num-1);
printf("%.2f\n",re[num-1-sa]);
}
return 0;
}
posted on 2010-08-18 14:39
崔佳星 阅读(1167)
评论(0) 编辑 收藏 引用