Description
相信大家都听说一个“百岛湖”的地方吧，百岛湖的居民生活在不同的小岛中，当他们想去其他的小岛时都要通过划小船来实现。现在*决定大力发展百岛湖，发展首先要解决的问题当然是交通问题，*决定实现百岛湖的全畅通！经过考察小组RPRush对百岛湖的情况充分了解后，决定在符合条件的小岛间建上桥，所谓符合条件，就是2个小岛之间的距离不能小于10米，也不能大于1000米。当然，为了节省资金，只要求实现任意2个小岛之间有路通即可。其中桥的价格为 100元/米。
Input
输入包括多组数据。输入首先包括一个整数T(T <= 200)，代表有T组数据。
每组数据首先是一个整数C(C <= 100),代表小岛的个数，接下来是C组坐标，代表每个小岛的坐标，这些坐标都是 0 <= x, y <= 1000的整数。
每组数据首先是一个整数C(C <= 100),代表小岛的个数，接下来是C组坐标，代表每个小岛的坐标，这些坐标都是 0 <= x, y <= 1000的整数。
Output
每组输入数据输出一行，代表建桥的最小花费，结果保留一位小数。如果无法实现工程以达到全部畅通，输出”oh!”.
Sample Input
2
2
10 10
20 20
3
1 1
2 2
1000 1000
2
10 10
20 20
3
1 1
2 2
1000 1000
Sample Output
1414.2
oh!
oh!
#include<stdio.h>
#include<algorithm>
#include<math.h>
#define Max 0x3f3f3f3f
using namespace std;
struct island
{
double x , y ;
}land[]; int n , fa[] ;
int in ; struct edge
{
int u , v ;
double w ;
}e[*+]; void binary (island a , int key , int l , int r )
{
if ( l >= r) {
return ;
}
int mid = (l + r) / ;
binary (a , key , l , mid ) ;
binary (a , key , mid + , r ) ;
double dis = (a.x - land[mid].x) * (a.x - land[mid].x) + (a.y - land[mid].y) * (a.y - land[mid].y) ; if ( dis <= * && dis >= * ) {
e[in].u = key ;
e[in].v = mid ;
e[in].w = sqrt (dis) ;
in++ ;
}
} bool cmp (edge a , edge b)
{
return a.w < b.w ;
} int find (int x)
{
return fa[x] == x ? x : find (fa[x]) ;
} void kruskal ()
{
sort ( e + , e + in , cmp ) ;
int x , y ;
double ans = ;
for (int i = ; i < in ; i++) {
x = find (e[i].u) ;
y = find (e[i].v) ;
if ( x != y) {
ans += e[i].w ;
fa[x] = y ;
}
}
printf ("%.1f\n" , 100.0 * ans ) ;
}
int main ()
{
// freopen ("a.txt" , "r" , stdin ) ;
int T;
scanf ("%d" , &T ) ;
int x , y ;
int cnt ;
while (T--) {
in = ;//RE 's reason
cnt = ;
scanf ("%d" , &n ) ;
for (int i = ; i <= n ; i++)
fa[i] = i ;
for (int i = ; i <= n ; i++) {
scanf ("%lf%lf" , &land[i].x , &land[i].y ) ;
}
for (int i = ; i < n ; i++ ) {//建立 u , v , w
binary ( land[i] , i , i + , n + ) ;
}
//To determine whether the connectivity
for (int i = ; i < in ; i++) {
x = find (e[i].u) ;
y = find (e[i].v) ;
fa[x] = y;
}
for (int i = ; i <= n ; i++) {
if (fa[i] == i )
cnt++ ;
if (cnt > )
break ;
} for (int i = ; i <= n ; i++)
fa[i] = i ; if ( cnt > )
puts ("oh!") ;
else
kruskal () ;
}
return ;
}
每组测试前要把edge的下标in初始化，为此re