bzoj2429: [HAOI]聪明的猴子（最小生成树）

bzoj题目链接

luogu题目连接

超级大水题，只比模板多了一个坐标操作！！！

题目大意：

1、坐标上有n个点，求最小生成树的边权最大值maxx。

2、求m只猴子，跳跃距离大于maxx的个数。

解题思路：

1、坐标上求距离，记得用double

2、跑最小生成树，然后逐一比较。

上代码：

#include<cstdio>#include<algorithm>#include<cmath>using namespace std;const int mx=;int m,n,maxx=0,len=0,f[mx];double bj[mx];struct nodb{int x,y;double c;}b[mx],e[mx*1000];struct nodz{double x,y; }z[mx];bool cmp(nodb x,nodb y) { return x.c<y.c; }int ch(int x) { if(x==f[x]) return x; return f[x]=ch(f[x]); }void ins(int x,int y){double t=sqrt((z[x].x-z[y].x)*(z[x].x-z[y].x)+(z[x].y-z[y].y)*(z[x].y-z[y].y));len++;e[len].x=x;e[len].y=y;e[len].c=t;}void kis(){int kk=0;for(int i=1;i<=n;i++) f[i]=i;sort(e+1,e+1+len,cmp);for(int i=1;i<=len;i++){int xx=ch(e[i].x);int yy=ch(e[i].y);if(xx!=yy) {f[xx]=yy;if(maxx<e[i].c) maxx=e[i].c;kk++;if(kk==n-1) break;}}}int main(){scanf("%d",&m);for(int i=1;i<=m;i++) scanf("%lf",&bj[i]);scanf("%d",&n); int x,y;for(int i=1;i<=n;i++){scanf("%lf %lf",&z[i].x,&z[i].y);}for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(i!=j){ins(i,j);}}}kis();int ans=0;for(int i=1;i<=m;i++) if(bj[i]>=maxx) ans++;printf("%d\n",ans);return 0;}

如果觉得《bzoj2429: [HAOI]聪明的猴子（最小生成树）》对你有帮助，请点赞、收藏，并留下你的观点哦！