P2504 [HAOI2006] 聪明的猴子

40 pts求调 orz

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,cnt,tot,ops;
double ans;
int f[5005],monkey[5005],a[2005][3];
struct Edeg{
	int u,v;
	double w;
}e[1000010];

bool cmp(Edeg a, Edeg b){
	return a.w < b.w;
}
int find(int v){
	return v == f[v]? v: f[v] = find(f[v]);
}

bool Union(int x,int y){
	int u = find(x);	
	int v = find(y);
	if(u != v){
		f[u] = v;
		return true;
	}
	return false;
}

int main(){
	cin >> n;
	for(int i=1;i<=n;i++){
		cin >> monkey[i];
	}
	cin >> m;
	for(int i = 1;i <= m;i++){
		cin >> a[i][1] >> a[i][2];
	}
	tot = 0;
	for(int i=1;i<=m;i++){
		for(int j=i+1;j<=m;j++){
			e[++tot].u = i;
			e[tot].v = j;
			e[tot].w = sqrt((a[i][1]-a[j][1])*(a[i][1]-a[j][1])+(a[i][2]-a[j][2])*(a[i][2]-a[j][2]));
		}
	}	
	sort(e+1,e+1+tot,cmp);
	for(int i = 1;i <= m;i++){
		f[i] = i;
	}
	for(int i=1;i<=tot;i++){
		if(Union(e[i].u,e[i].v)){
			ans = max(ans,e[i].w);
			if(++cnt == n-1){
				break;
			}
		}
	}
	for(int i=1;i<=n;i++){
		if(monkey[i] >= ans){
			ops++;
		}
	}
	cout << ops;
	return 0;
}