题目就是给出一个笛卡尔坐标系,然后给出一些点,问题就是要求最小生成树。我以前没有做过这样的,因为这里,一个点到另一个点的距离没有给出。难道要把一个点到所有的点的距离都求出来?那样的话时间复杂度就太高了吧?
我发现我现在还是太贪求速度,我确实是想到了这里,但是我没有去做,去写,而是去找别人的代码,先看看别人是怎么写的,然后我再写。其实,他们和我的算法思想是一样的。我以后要尽力改正这一个不好的习惯。这样非常不利于我学习算法。加油!
#include <stdio.h>
#include <math.h>
#define DEBUG 1
const double Max = 0x7fffffff ;
const int N = 111 ;
int n, used[N], closest[N] ;
double map[N][N], pos[N][2], dis[N] ;
double Distance( double *a, double *b )
{
return sqrt( (a[0]-b[0])*(a[0]-b[0]) + (a[1]-b[1])*(a[1]-b[1]) ) ;
}
double Prim( )
{
int i, j, index ;
double min, len ;
for( i=1; i<=n; ++i ){
used[i] = 0 ;
dis[i] = map[1][i] ;
}
used[1] = 1 ;
len = 0 ;
for( i=1; i<n; ++i ){
min = Max ;
for( j=1; j<=n; ++j ){
if( !used[j] && min>dis[j] ){
index = j ;
min = dis[j] ;
}
}
used[index] = 1 ;
len += dis[index] ;
for( j=1; j<=n; ++j ){
if( !used[j] && dis[j]>map[j][index] )
dis[j] = map[j][index] ;
}
}
return len ;
}
int main()
{
#if DEBUG
freopen("C:\\Documents and Settings\\Administrator\\桌面\\in.txt","r",stdin);
freopen("C:\\Documents and Settings\\Administrator\\桌面\\out.txt","w",stdout);
#endif
int i, j ;
while( EOF != scanf("%d", &n ) ){
for( i=1; i<=n; ++i )
for( j=1; j<=n; ++j )
map[i][j] = Max ;
for( i=1; i<=n; ++i )
scanf("%lf%lf", &pos[i][0], &pos[i][1] ) ;
for( i=1; i<=n; ++i ){
for( j=i+1; j<=n; ++j ){
map[i][j] = map[j][i] = Distance( pos[i], pos[j] ) ;
}
}
printf("%.2lf\n", Prim( ) ) ;
}
return 0 ;
}