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 ;}