POJ2349+Prim

ゝ一纸荒年。 2021-12-14 00:35 162阅读 0赞

Prim！

/*
    prim
    题意：给定一些点，一些卫星，一个卫星能连接两个点，点和点之间通信有一定的距离限制。
    问能使得所有的点联通的最小距离。
    */
    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<algorithm>
    #include<iostream>
    #include<queue>
    #include<map>
    #include<stack>
    #include<set>
    #include<math.h>
    using namespace std;
    typedef long long int64;
    //typedef __int64 int64;
    typedef pair<int64,int64> PII;
    #define MP(a,b) make_pair((a),(b)) 
    const int maxn = 505;
    const int inf = 0x7fffffff;
    const double pi=acos(-1.0);
    const double eps = 1e-8;
    
    struct Node{
    	double x,y;
    }a[ maxn ];
    int vis[ maxn ];
    double dis[ maxn ];
    double mat[ maxn ][ maxn ];
    
    double dist( Node a,Node b ){
    	return sqrt( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
    }
    
    void init( int n ){
    	for( int i=1;i<=n;i++ ){
    		for( int j=1;j<=n;j++ ){
    			mat[i][j] = dist( a[i],a[j] );
    		}
    	}
    	return ;
    } 
    
    void prim( int n ){
    	for( int i=1;i<=n;i++ ){
    		vis[ i ] = 0;
    		dis[ i ] = mat[1][i];
    	}
    	vis[ 1 ] = 1;
    	for( int i=1;i<=n;i++ ){
    		int M = inf;
    		int id = -1;
    		for( int j=1;j<=n;j++ ){
    			if( vis[ j ]==0&&M>dis[j] ){
    				M = dis[ j ];
    				id = j;
    			}
    		}
    		if( id==-1 ) return ;
    		vis[ id ] = 1;
    		for( int j=1;j<=n;j++ ){
    			if( vis[j]==0&&dis[j]>mat[ id ][ j ] ){
    				dis[ j ] = mat[ id ][ j ];
    			}
    		}
    	}
    	return ;
    }
    
    int main(){
    	int T;
    	scanf("%d",&T);
    	while( T-- ){
    		int s,n;
    		scanf("%d%d",&s,&n);
    		for( int i=1;i<=n;i++ )
    			scanf("%lf%lf",&a[i].x,&a[i].y);
    		init( n );
    		prim( n );
    		sort( dis+1,dis+1+n );
    		//for( int i=1;i<=n;i++ )
    		//	printf("%lf ",dis[ i ]);
    		//puts("");
    		printf("%.2lf\n",dis[ n-s+1 ]);
    	}
    	return 0;
    }

转载于:https://www.cnblogs.com/james1207/p/3268779.html