Bzoj 2429
coc youyl
posted @ 2015年7月02日 20:59
in bzoj
, 1019 阅读
题目分类:最小生成树
题意:
给出平面上n个点和m个猴子的跳跃能力,问哪些猴子能跳到所有的树上。
题解:
求出最小生成树,然后将猴子跳跃能力和最大边作比较。
程序:
#include<cstdio> #include<utility> #include<algorithm> using namespace std; int fat[1200]; inline int fnd(int x) { if(fat[x]==x)return x; return fat[x]=fnd(fat[x]); } int n,cnt,xx[1200],yy[1200],jum[1200],m; pair<int,pair<int,int> >a[1200000]; inline int sqr(int x) { return x*x; } int ans,res; int main() { scanf("%d",&m); for (int i=1;i<=m;i++) { scanf("%d",&jum[i]); } scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d %d",&xx[i],&yy[i]); } for (int i=1;i<n;i++) { fat[i]=i; for (int j=i+1;j<=n;j++) { cnt++; a[cnt].second.first=i; a[cnt].second.second=j; a[cnt].first=sqr(xx[i]-xx[j])+sqr(yy[i]-yy[j]); } } sort(a+1,a+cnt+1); for (int i=1;i<=cnt;i++) { int x1=a[i].second.first,x2=a[i].second.second; if(fnd(x1)!=fnd(x2)) { ans=a[i].first; fat[fnd(x1)]=fnd(x2); } } for (int i=1;i<=m;i++) { if(ans<=sqr(jum[i]))res++; }printf("%d\n",res); return 0; }
2022年8月09日 01:25
Zen Internet Broadband is considered as the fastest & reliable broadband for both home & business purpose. The company is having the strength of approximately 413 employees & all of them being dedicated & hard working people making the internet services very reliable. ZENBroadband Because of the hard work of the employees as well as CEO (Paul Stobard) & Chairman (Richard Tang), the company won several awards in 2006 at ISPA i.e. Internet Service Provider’s Association.