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

MST的板题，MST搞出来，再拿每一个猴子比一比就好

#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;

double w[M],cpt[N],MX;

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(){