poj 2349解题报告

想比赛前吧模板整理好,就做了一道这个题看看模板

题意:有P个点,用坐标给出,有两种联系方式:1每个点可以和距离在D以内的点相互联系,2有S个专门的卫星通道,两个点直接联系;

求D最小多少可以把这个图连起来

题解:首先不考虑S个卫星通道,先求最小生成树,用卫星通道把最小生成树中最大的S-1个边代替掉,然后剩下的最大的那条边的值

就是能把整个图连起来的D的最小值

#include <iostream>#include <cstring>#include <cstdio>#include <cmath>#include <algorithm>using namespace std ;const int MAXN = 505 ;struct  Edge{    int  start , end ;    double length ;    bool visit ;} edge[MAXN * MAXN] ;struct  Point{    int  x , y ;} point[MAXN] ;int  father[MAXN] , Count ;bool mark[MAXN] , vis[MAXN] ;double  getlength( Point a , Point b ){    double len ;    len = sqrt( double ( ( a.x - b.x ) * ( a.x - b.x ) + ( a.y - b.y ) * ( a.y - b.y ) ) ) ;    return len ;}bool  cmp( Edge a , Edge b ){    return a.length < b.length ;}int  find( int x ){    if( father[x] == x ) return x ;    father[x] = find( father[x] ) ;    return father[x]              ;}bool Union( int x , int y ){    int  f1 = find( x ) ;    int  f2 = find( y ) ;    if( f1 == f2 ) return false ;    else if( f1 < f2 ) father[f1] = f2 ;    else father[f2] = f1 ;    return true ;}double kruskal( int n ){    int  i , j = 0 ;    double sum = 0 ;    for( i = 0 ; i < n ; i ++ )        father[i] = i ;    sort( edge , edge + Count , cmp ) ;    for( i = 0 ; i < Count && j < n ; i ++ )    {        if( Union( edge[i].start , edge[i].end ) )        {            sum += edge[i].length  ;            edge[i].visit  = 1 ;            j ++ ;        }    }    return sum ;}int  main(){    int  T , S , P ;    int  i , j ;    scanf( "%d" , & T ) ;    while( T -- )    {        memset( mark , 0 , sizeof( mark ) ) ;        memset( vis  , 0 , sizeof( vis  ) ) ;        Count = 0 ;        scanf( "%d%d" , & S , & P ) ;        for( i = 0 ; i < P ; i ++ )            scanf( "%d%d" , & point[i].x , & point[i].y ) ;        Count = 0 ;        for( i = 0 ; i < P - 1 ; i ++ )            for( j = i + 1 ; j < P ; j ++ )            {                edge[Count].start = i ;                edge[Count].end   = j ;                edge[Count].length = getlength( point[i] , point[j] ) ;                edge[Count].visit = 0 ;                Count ++ ;            }        kruskal( P ) ;        for( i = Count - 1 ; i >= 0 ; i -- ){            if( edge[i].visit )            {                S -- ;                if( S == 0 ) break ;            }        }        printf( "%.2f\n" , edge[i].length ) ;    }    return 0 ;}