poj 2349解題報告

想比賽前吧模板整理好,就做了一道這個題看看模板

題意:有P個點,用坐標給出,有兩種聯系方式:1每個點可以和距離在D以內的點相互聯系,2有S個專門的衛星通道,兩個點直接聯系;

求D最小多少可以把這個圖連起來

題解:首先不考慮S個衛星通道,先求最小生成樹,用衛星通道把最小生成樹中最大的S-1個邊代替掉,然後剩下的最大的那條邊的值

就是能把整個圖連起來的D的最小值

[cpp] 
#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 ; 
}