学步园

题目：在二维平面上有很多个城市，现在要把所有城市都连接起来，求最长边的小代价。其中某些城市可以直接用卫星连接、没有长度。

分析：MST、并查集。最小生成树，这里利用kruskar算法求解。求出最小生成树上的第p-s长的边即为结果。

注意：题目的描述有点纠结。既不是每个点放一个卫星、也不是每个边放一个卫星，而是最大边放2个其他边放1个。

#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 );
		}
		
		//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;
}