[BZOJ2429][HAOI2006]聪明的猴子(最小生成树)
2024-08-28 12:14:04
性质:最小生成树上任意两点间的最大边权,一定是这两点间所有路径的最大边权中最小的。证明显然。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define rep(i,l,r) for (int i=(l); i<=(r); i++)
using namespace std; const int N=,M=;
int n,m,tot,ans,mx,k,a[N],fa[N];
struct P{ int x,y; }p[N];
struct E{ int u,v,w; }e[M];
bool operator <(const E &a,const E &b){ return a.w<b.w; }
int sqr(int x){ return x*x; }
int get(int x){ return (fa[x]==x) ? x : fa[x]=get(fa[x]); } int main(){
scanf("%d",&m);
rep(i,,m) scanf("%d",&a[i]);
scanf("%d",&n);
rep(i,,n) scanf("%d%d",&p[i].x,&p[i].y),fa[i]=i;
rep(i,,n-) rep(j,i+,n) e[++tot]=(E){i,j,sqr(p[i].x-p[j].x)+sqr(p[i].y-p[j].y)};
sort(e+,e+tot+);
rep(i,,tot){
int u=e[i].u,v=e[i].v;
if (get(u)==get(v)) continue;
k++; mx=max(mx,e[i].w);
if (k==n-) break;
fa[get(u)]=get(v);
}
rep(i,,m) if (sqr(a[i])>=mx) ans++;
printf("%d\n",ans);
return ;
}
最新文章
- Spring MVC MultipartFile实现图片上传
- String字符串类课后作业
- bg激活后台运行的服务
- Java中Runnable和Thread
- Magicodes.WeiChat——使用AntiXssAttribute阻止XSS(跨站脚本攻击)攻击
- $apply方法的作用
- wait(...) notify() notifyAll()
- Django环境搭建和项目创建
- sublimeText3安装package control和禁止弹出更新下载弹窗
- Visual Studio Code中文文档
- android插件技术-apkplug于OSGI服务基础-08
- Flex入门(三)——微架构之Cairngorm
- vue-router自动判断左右翻页转场动画
- python 中几种基本的矩阵操作应用
- io系列之其他类
- SoapUI&#160;访问代理设置
- Building an (awesome) API with NancyFX 2.0 + Dapper
- jar依赖
- Linux抓包工具
- UVa 10048 噪音恐惧症(Floyd)