新闻详情

新闻详情

首页 / 资讯中心 / 详情

奥赛一本通 1437 扩散

发布时间:2026/9/15 9:03:06来源:尧图网络
奥赛一本通 1437 扩散
1437 扩散题目大意给定平面上的 $n$ 个点每过一个单位时间每个点都会向四个方向扩散一个距离求它们形成连通块的最短时间。知识要点二分、并查集、生成树解题思路 1两个点之间直接连通的时间就是它们曼哈顿距离的一半可以二分枚举时间利用并查集检查是否所有节点均连通。参考代码 1#includebits/stdc.husingnamespacestd;constintN55;intn,x[N],y[N],fa[N];intfind(intx){if(fa[x]x)returnx;returnfa[x]find(fa[x]);}boolcheck(intt){for(inti1;in;i)fa[i]i;for(inti1;in;i)for(intji1;jn;j){if(abs(x[i]-x[j])abs(y[i]-y[j])2*t)fa[find(i)]find(j);}intcnt0;for(inti1;in;i)if(fa[i]i)cnt;returncnt1;}intmain(){scanf(%d,n);for(inti1;in;i)scanf(%d%d,x[i],y[i]);intl0,r1e9,t;while(lr){t(lr)/2;if(check(t))rt;elselt1;}printf(%d\n,l);return0;}解题思路 2所有的点都连通意味着至少形成了一棵生成树需要的时间就是最长的那条边相当于求完全图的一个最小瓶颈树使用 Prim 算法的时间复杂度为 $O(n^2)$。参考代码 2#includebits/stdc.husingnamespacestd;constintN55;intn,x[N],y[N],v[N],dis[N];intPrim(){intans0;memset(dis,0x3f,sizeof(dis));dis[1]0;for(intk1;kn;k){inti0,j;for(j1;jn;j)if(!v[j]dis[i]dis[j])ij;v[i]1,ansmax(ans,dis[i]);for(j1;jn;j)if(!v[j])dis[j]min(dis[j],abs(x[i]-x[j])abs(y[i]-y[j]));}returnans;}intmain(){scanf(%d,n);for(inti1;in;i)scanf(%d%d,x[i],y[i]);printf(%d\n,(Prim()1)/2);return0;}
网站建设高端定制企业官网
RELATED

相关资讯

更多精彩内容,欢迎继续阅读

较早相关资讯

最新相关资讯

Faker::Movies::StarWars 全解析:用 Ruby Faker 生成星球大战风格的假数据 2026/9/15 9:51:17

Faker::Movies::StarWars 全解析:用 Ruby Faker 生成星球大战风格的假数据

Faker::Movies::StarWars 全解析:用 Ruby Faker 生成星球大战风格的假数据 【免费下载链接】faker A library for generating fake data such as names, addresses, and phone numbers. 项目地址: https://gitcode.com/GitHub_Trending/fake/faker 导读 Fak…

阅读更多 →
4070Ti单卡跑通纯PyTorch中文LLM:40M参数实战指南 2026/9/15 9:51:17

4070Ti单卡跑通纯PyTorch中文LLM:40M参数实战指南

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

阅读更多 →
WorkBuddy工作流实战:零代码构建可审计AI Agent自动化 2026/9/15 9:51:17

WorkBuddy工作流实战:零代码构建可审计AI Agent自动化

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

阅读更多 →
LunaTranslator 在 HOOK 模式下临时使用 OCR:一次OCR与再次OCR按钮/快捷键完全指南 2026/9/15 9:51:17

LunaTranslator 在 HOOK 模式下临时使用 OCR:一次OCR与再次OCR按钮/快捷键完全指南

LunaTranslator 在 HOOK 模式下临时使用 OCR:一次OCR与再次OCR按钮/快捷键完全指南 【免费下载链接】LunaTranslator 视觉小说翻译器 / Visual Novel Translator 项目地址: https://gitcode.com/GitHub_Trending/lu/LunaTranslator LunaTranslator 是一款面向…

阅读更多 →
deck.gl PointLight 点光源完全指南:参数详解、坐标系统与实战接入 2026/9/15 9:51:17

deck.gl PointLight 点光源完全指南:参数详解、坐标系统与实战接入

deck.gl PointLight 点光源完全指南:参数详解、坐标系统与实战接入 【免费下载链接】deck.gl WebGL2 powered visualization framework 项目地址: https://gitcode.com/GitHub_Trending/de/deck.gl 导读 PointLight 是 deck.gl 核心库中用于模拟"从某一…

阅读更多 →
ScyllaDB 容量与限制指南:集群、CQL 与数据模型的上限全解析 2026/9/15 9:48:17

ScyllaDB 容量与限制指南:集群、CQL 与数据模型的上限全解析

ScyllaDB 容量与限制指南:集群、CQL 与数据模型的上限全解析 【免费下载链接】scylladb NoSQL data store using the Seastar framework, compatible with Apache Cassandra and Amazon DynamoDB 项目地址: https://gitcode.com/GitHub_Trending/sc/scylladb …

阅读更多 →

今日资讯

本周资讯

本月资讯

看完文章仍有疑问?

联系尧图顾问,获取一对一建站咨询

立即免费咨询 📞 400-888-8888
📞