這個題首先要把輸入的坐標轉化成鄰接矩陣的形式。之后再利用鄰接矩陣使用普里姆算法計算最小生成樹。并對其中的邊進行排序。找出減去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
崔佳星 閱讀(1173)
評論(0) 編輯 收藏 引用