題目：在二維平面上有很多個城市，現在要把所有城市都連接起來，求最長邊的小代價。其中某些城市可以直接用衛星連接、沒有長度。 分析：MST、並查集。最小生成樹，這裡利用kruskar算法求解。求出最小生成樹上的第p-s長的邊即為結果。 注意：題目的描述有點糾結。既不是每個點放一個衛星、也不是每個邊放一個衛星，而是最大邊放2個其他邊放1個。 [cpp] #include <stdio.h> #include <stdlib.h> #include <math.h> //union_set_begin int sets[ 501 ]; int rank[ 501 ]; void union_set( int n ) { for ( int i = 0 ; i <= n ; ++ i ) { rank[i] = 0; sets[i] = i; } } int Find( int a ) { if ( a != sets[a] ) sets[a] = Find( sets[a] ); return sets[a]; } int Union( int a, int b ) { if ( rank[a] > rank[b] ) sets[b] = a; else { sets[a] = b; if ( rank[a] == rank[b] ) rank[b] ++; } } //union_set_end typedef struct point { int x,y; }point; point P[501]; typedef struct edge { int u,v; double l; }edge; edge E[ 125251 ]; int cmp( const void *a, const void *b ) { edge *p = (edge *)a; edge *q = (edge *)b; if ( p->l < q->l ) return -1; else return 1; } int main() { int N,s,p,x,y; while ( scanf("%d",&N) != EOF ) while ( N -- ) { scanf("%d%d",&s,&p); union_set( p ); for ( int i = 1 ; i <= p ; ++ i ) scanf("%d%d",&P[i].x,&P[i].y); int e_count = 0; for ( int i = 1 ; i <= p ; ++ i ) for ( int j = 1 ; j < i ; ++ j ) { E[e_count].u = i; E[e_count].v = j; x = P[i].x - P[j].x; y = P[i].y - P[j].y; E[e_count ++].l = sqrt( x*x+y*y+0.0 ); } www.2cto.com //kruskar qsort( E, e_count, sizeof(edge), cmp ); int a,b,count = 0; for ( int i = 0 ; i < e_count ; ++ i ) { a = Find( E[i].u ); b = Find( E[i].v ); if ( a != b ) { Union( a, b ); if ( ++ count == p-s ) { printf("%.2lf\n",E[i].l); break; } } } } return 0; }
