题意：给定n个坐标，求最小生成树。
先将nike和apple之间的边加进来，并更新mat[nike][apple]=0,再贪心即可。
或者：先把vis[ nike ]=vis[ apple ]=1,但是同时要更新dis[ i ]=min( mat[apple][i],mat[nike][i]);
View Code
1 #include<stdio.h> 2 #include<string.h> 3 #include<math.h> 4 #include<algorithm> 5 using namespace std; 6 const int maxn = 255; 7 const int inf = 999999; 8 int vis[ maxn ]; 9 double mat[ maxn ][ maxn ],dis[ maxn ]; 10 struct node{ 11 int x,y; 12 }a[ maxn ]; 13 int n; 14 int nike,apple; 15 16 double dist( int x1,int y1,int x2,int y2 ){ 17 double ans=(x1-x2)*(x1-x2)*1.0+(y1-y2)*(y1-y2)*1.0; 18 return sqrt( ans ); 19 } 20 21 double prim( ){ 22 double sum=0; 23 sum+=mat[ nike ][ apple ]; 24 vis[ nike ]=vis[ apple ]=1; 25 for( int i=1;i<=n;i++ ) 26 dis[ i ]=min(mat[ apple ][ i ],mat[ nike ][ i ]); 27 for( int i=0;i<n;i++ ){ 28 int k=-1; 29 double max; 30 max=inf*1.0; 31 for( int j=1;j<=n;j++ ){ 32 if( vis[ j ]==0 && max>dis[ j ] ){ 33 k=j,max=dis[ j ]; 34 } 35 } 36 if( k==-1 ) return sum; 37 vis[ k ]=1; 38 sum+=max; 39 for( int j=1;j<=n;j++ ){ 40 if( vis[ j ]==0 && dis[ j ]>mat[ k ][ j ] ){ 41 dis[ j ]=mat[ k ][ j ]; 42 } 43 } 44 } 45 return sum; 46 } 47 48 int main(){ 49 while( scanf("%d",&n)!=EOF,n ){ 50 scanf("%d%d",&nike,&apple); 51 memset( vis,0,sizeof( vis )); 52 for( int i=1;i<=n;i++ ) 53 scanf("%d%d",&a[ i ].x,&a[ i ].y),a[i].x+=100,a[i].y+=100; 54 for( int i=1;i<=n;i++ ){ 55 for( int j=1;j<=n;j++ ){ 56 if( i!=j ) 57 mat[ i ][ j ] = dist( a[ i ].x,a[ i ].y,a[ j ].x,a[ j ].y ); 58 else 59 mat[ i ][ j ]=inf*1.0; 60 } 61 } 62 double ans=prim(); 63 printf("%.2lf\n",ans); 64 } 65 return 0; 66 }