[Time Gate]
https://www.luogu.org/problemnew/show/P2504
【解题思路】
这题和P2872道路建设几乎差不多,主要思路:
算两点之间距离,然后跑Kruskal找最大的边,和每只猴子跳跃距离比较一下,同步计数即可
【code】
1 #include <cstdio> 2 #include <cmath> 3 #include <algorithm> 4 using namespace std; 5 int n,m,d,cnt,ans; 6 int x[1005],y[1005],fa[1005],monkey[1005]; 7 struct Node{ 8 int x; 9 int y; 10 double dis; 11 }a[1000005]; 12 inline int Find(int i){ 13 if(fa[i]==i)return i; 14 return fa[i]=Find(fa[i]); 15 } 16 inline void Union(int x,int y){ 17 int f1=Find(x); 18 int f2=Find(y); 19 if(f1!=f2)fa[f1]=f2; 20 return; 21 } 22 inline bool cmp(Node a,Node b){ 23 if(a.dis==b.dis)return a.x<b.x; 24 return a.dis<b.dis; 25 } 26 int main(){ 27 scanf("%d",&m); 28 for(register int i=1;i<=m;i++) 29 scanf("%d",&monkey[i]); 30 scanf("%d",&n); 31 for(register int i=1;i<=n;i++) 32 fa[i]=i; 33 for(register int i=1;i<=n;i++) 34 scanf("%d%d",&x[i],&y[i]); 35 for(register int i=1;i<=n;i++) 36 for(register int j=i+1;j<=n;j++){ 37 a[++cnt].x=i; 38 a[cnt].y=j; 39 a[cnt].dis=(double)sqrt((double)(x[i]-x[j])*(double)(x[i]-x[j])+(double)(y[i]-y[j])*(double)(y[i]-y[j])); 40 } 41 sort(a+1,a+cnt+1,cmp); 42 for(register int i=1;i<=cnt;i++){ 43 if(Find(a[i].x)!=Find(a[i].y)){ 44 Union(a[i].x,a[i].y); 45 d=a[i].dis; 46 } 47 } 48 for(register int i=1;i<=m;i++) 49 if(monkey[i]>=d)ans++; 50 printf("%d\n",ans); 51 return 0; 52 }