UVa 10369 - Arctic Network
题目：在二维平面上有很多个城市，现在要把所有城市都连接起来，求最长边的小代价。其中某些城市可以直接用卫星连接、没有长度。分析：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.zzzyk.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;
}
补充：软件开发 , C++ ,
