神tm的题。。。
众所周知这题是最小生成树的说。。还有大神说是最小瓶颈生成树（%%%D飞了
结果我就乱搞了。
可以发现，假如一个跳的很远的猴子无法到达全部，那么比他跳的近的猴子肯定不行的，那我想二分猴子咯，然后O(m^2)宽搜一波O(logn*m^2)还是能狗过去的，结果WA了，搞到数据才发现，wc，还有什么猴子都跳不过去的数据，然而我ans没有初始化。。
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; struct tree { int x,y; }t[1100];int m; int n,a[510]; bool v[1100]; int list[1100]; int dis(tree n1,tree n2) { return (n1.x-n2.x)*(n1.x-n2.x)+(n1.y-n2.y)*(n1.y-n2.y); } bool check(int k) { memset(v,false,sizeof(v));v[1]=true; int head=1,tail=2,rea=1;list[1]=1; while(head!=tail) { tree tno=t[list[head]]; for(int i=1;i<=m;i++) { if(v[i]==false&&dis(tno,t[i])<=a[k]*a[k]) { v[i]=true; rea++; list[tail]=i; tail++; } } head++; } if(rea==m)return true; else return false; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); sort(a+1,a+n+1); scanf("%d",&m); for(int i=1;i<=m;i++)scanf("%d%d",&t[i].x,&t[i].y); int l=1,r=n,ans=n+1; while(l<=r) { int mid=(l+r)/2; if(check(mid)==true) { ans=mid; r=mid-1; } else l=mid+1; } printf("%d\n",n-ans+1); return 0; }
原文：http://www.cnblogs.com/AKCqhzdy/p/7898954.html