本題は,最小生成ツリーを求め,クルーズカールアルゴリズムを用いて解決できる.しかし、ここでのエッジは、条件に合致するエッジをエッジセットに追加する必要があります.これにより、クルーズカールアルゴリズムを使用して、ソート+を検索して連通性を検出し、最終的に結論を出すことができます.ここでエッジの重みを扱う際にdoubleタイプのデータを直接処理しないのは、浮動小数点型のデータを扱う場合、比較的サイズが間違えやすいため、保存されている未開二乗以前のint値であり、タイトルデータからこの値が100-100000の間にあることがわかるので、保存して並べ替えるのも便利です.

滞りなく工事を再開する

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 12183    Accepted Submission(s): 3744
Problem Description
「百島湖」という場所を聞いたことがあると思いますが、百島湖の住民は異なる島に住んでいて、他の島に行きたいときはボートを漕ぐことで実現します.現在、政府は百島湖を大いに発展させることを決定し、発展がまず解決しなければならない問題はもちろん交通問題であり、政府は百島湖の全開通を実現することを決定した.調査チームRPRushが百島湖の状況を十分に理解した後、条件に合った小島の間に橋を建てることにした.条件に合ったのは、2つの小島の間の距離が10メートル以上、1000メートル以上ではないということだ.もちろん、お金を節約するためには、任意の2つの島の間に道があることだけを要求すればいい.このうち橋の価格は100元/メートルです.
 
Input
入力には複数のデータが含まれます.入力は、まず、Tセットデータを表す整数T(T<=200)を含む.
各グループのデータは、まず整数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
   
   
   
   

 
Sample Output

   
   
   
   

    
    
    
    1414.2
oh!
   
   
   
   

 
Author
8600
 
Source
2008浙大大学院生再試験ウォーミングアップ試合(2)——全真シミュレーション
 

#include <cstdio>
#include <cstdlib>
#include <cmath>


const int MAX = 105;


const int L = 100;
const int R = 1000000;


int cnt;


double total;




typedef struct{
	int x,y;
	int cost;
}Point;


Point pot[MAX*MAX];//       ，  WA   ，              n*(n-1)/2


int pre[MAX],px[MAX],py[MAX];


int cal_len(int n){
	int i,j,tx,ty,len,pos;


	pos = 0;


	for(i=0;i<n;++i){
		for(j=i+1;j<n;++j){
			tx = px[i]-px[j];
			tx *= tx;
			ty = py[i]-py[j];
			ty *= ty;
			len = tx + ty;
			if(len>=L && len<=R){
				pot[pos].x = i;
				pot[pos].y = j;
				pot[pos].cost = len;
				++pos;
			}
		}
	}
	return pos;
}


void init(int n){
	int i;


	cnt = n-1;
	total = 0.0;
	for(i=0;i<n;++i){
		pre[i] = i;
	}
}


int root(int x){
	if(x!=pre[x]){
		pre[x] = root(pre[x]);
	}
	return pre[x];
}


int merge(int x,int y){
	int ret = 0;
	int fx = root(x);
	int fy = root(y);


	if(fx!=fy){
		--cnt;
		pre[fx] = fy;
		ret = 1;
	}
	return ret;
}


int cmp(const void *a,const void *b){
	Point *pa = (Point *)a;
	Point *pb = (Point *)b;


	return pa->cost-pb->cost;
}


int main(){
	int i,t,n;


	//freopen("in.txt","r",stdin);
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		
		init(n);


		for(i=0;i<n;++i){
			scanf("%d %d",&px[i],&py[i]);
		}


		int ln = cal_len(n);


		if(ln<n-1){
			printf("oh!
");
			continue;
		}


	//	printf("%d******
",ln);


		qsort(pot,ln,sizeof(Point),cmp);


		for(i=0;i<ln;++i){
			if(merge(pot[i].x,pot[i].y)==1){
				total += sqrt(pot[i].cost*1.0);
			}
		}


		if(cnt!=0){
			printf("oh!
");
			continue;
		}else{
			printf("%0.1lf
",total*100);
			continue;
		}
	}
	return 0;
}