# 【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(){
tot=read(); for (int i=1;i<=tot;i++) val[i] = read();
n = read(); for (int i=1;i<=n;i++) {
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;
}


## 2 thoughts to “【BZOJ 2429】[HAOI2006] 聪明的猴子”

1. Can I just say what a relief to find someone who actually knows what theyre talking about on the internet. You positively know find out how to convey an issue to mild and make it important. Extra folks need to learn this and perceive this aspect of the story. I cant imagine youre not more widespread because you definitely have the gift.

2. As a Newbie, I am constantly searching online for articles that can aid me. Thank you