【BZOJ 2429】[HAOI2006] 聪明的猴子

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2429

MST的板题,MST搞出来,再拿每一个猴子比一比就好
好吧,其实我是来练Boruvka的……

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define pow(x) ((x)*(x))
using namespace std;

const int N = 1000+9;
const int M = 1000000+9;
const double EPS = 1e-8;

int X[N],Y[N],to[M],nxt[M],head[N],val[N],tot,n,m,vout,fa[N],cot[N];
double w[M],cpt[N],MX;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline void AddEdge(int i, int j){
	double tmp = sqrt(pow(X[i]-X[j])+pow(Y[i]-Y[j]));
	to[++m] = j; nxt[m] = head[i]; w[m] = tmp; head[i] = m;
	to[++m] = i; nxt[m] = head[j]; w[m] = tmp; head[j] = m;
}

inline int find(int w){
	int f=fa[w],tmp;
	while (fa[f] != f) f = fa[f];
	while (w != f) tmp=fa[w],fa[w]=f,w=tmp;
	return f;
}

inline void Boruvka(){
	for (int i=1;i<=n;i++) fa[i] = i;
	for (int t=n;t>1;) {
		memset(cot,0,sizeof(cot));
		for (int i=1,f1,f2;i<=n;i++) for (int j=head[i];j;j=nxt[j]){
			f1 = find(i); f2 = find(to[j]);
			if (f1 != f2) {
				if (!cot[f1] || cpt[f1] > w[j]) cot[f1] = f2, cpt[f1] = w[j];
				if (!cot[f2] || cpt[f2] > w[j]) cot[f2] = f1, cpt[f2] = w[j];
			} 	
		}
		
		for (int i=1,ft;i<=n;i++) if (fa[i] == i) {
			if ((ft = find(cot[i])) != i) {
				fa[ft] = i; MX = max(MX, cpt[i]); t--;
			}
		} 
	}
}

int main(){
	tot=read(); for (int i=1;i<=tot;i++) val[i] = read();
	n = read(); for (int i=1;i<=n;i++) {
		X[i] = read(); Y[i] = read();
		for (int j=1;j<i;j++) AddEdge(i,j);
	}
	Boruvka();
	for (int i=1;i<=tot;i++) if (EPS+val[i] >= MX) vout++;
	printf("%d\n",vout);
	return 0;
}