题目传送门: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; }