【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;
}

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.

Leave a Reply to oprolevorter Cancel reply

Your email address will not be published. Required fields are marked *