1125. 牛的旅行 (Floyd算法,最短路)
1125. 牛的旅行 - AcWing题库
农民John的农场里有很多牧区,有的路径连接一些特定的牧区。
一片所有连通的牧区称为一个牧场。
但是就目前而言,你能看到至少有两个牧区不连通。
现在,John想在农场里添加一条路径(注意,恰好一条)。
一个牧场的直径就是牧场中最远的两个牧区的距离(本题中所提到的所有距离指的都是最短的距离)。
考虑如下的两个牧场,每一个牧区都有自己的坐标:
图 1 是有 5 个牧区的牧场,牧区用“*”表示,路径用直线表示。
图 1 所示的牧场的直径大约是 12.07106, 最远的两个牧区是 A 和 E,它们之间的最短路径是 A-B-E。
图 2 是另一个牧场。
这两个牧场都在John的农场上。
John将会在两个牧场中各选一个牧区,然后用一条路径连起来,使得连通后这个新的更大的牧场有最小的直径。
注意,如果两条路径中途相交,我们不认为它们是连通的。
只有两条路径在同一个牧区相交,我们才认为它们是连通的。
现在请你编程找出一条连接两个不同牧场的路径,使得连上这条路径后,所有牧场(生成的新牧场和原有牧场)中直径最大的牧场的直径尽可能小。
输出这个直径最小可能值。
输入格式
第 1 行:一个整数 N, 表示牧区数;
第 2 到 N+1 行:每行两个整数 X,Y, 表示 N 个牧区的坐标。每个牧区的坐标都是不一样的。
第 N+2 行到第 2*N+1 行:每行包括 N 个数字 ( 0或1 ) 表示一个对称邻接矩阵。
例如,题目描述中的两个牧场的矩阵描述如下:
A B C D E F G H
A 0 1 0 0 0 0 0 0
B 1 0 1 1 1 0 0 0
C 0 1 0 0 1 0 0 0
D 0 1 0 0 1 0 0 0
E 0 1 1 1 0 0 0 0
F 0 0 0 0 0 0 1 0
G 0 0 0 0 0 1 0 1
H 0 0 0 0 0 0 1 0
输入数据中至少包括两个不连通的牧区。
输出格式
只有一行,包括一个实数,表示所求答案。
数字保留六位小数。
数据范围
1≤N≤150
0≤X,Y≤105
输入样例:
8
10 10
15 10
20 10
15 15
20 15
30 15
25 10
30 10
01000000
10111000
01001000
01001000
01110000
00000010
00000101
00000010
输出样例:
22.071068
解析:
1.答案大于等于所有连通块直径的最大值
2.经过新边的最长的最短路径
具体过程:
1.用floyd算法求出任意两点之间的最短距离
2.求出max[i],表示和i连通的且距离i最远的点的距离
3.情况1:所有max[i]的最大值
情况2:枚举在哪两个点之间连边。i,j,需要满足d[i,j]=INF, maxd[i]+dist[i,j]+maxd[j]
#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<math.h>
#include<map>
#include<sstream>
#include<deque>
#include<unordered_map>
using namespace std;
const int N = 150 + 5;
const double INF = 1e20;
int n;
char g[N][N];
double d[N][N],maxd[N];
typedef pair<double, double> PII;
PII p[N];double get_dist(PII a, PII b) {double dx = a.first - b.first;double dy = a.second - b.second;return sqrt(dx * dx + dy * dy);
}int main() {cin >> n;for (int i = 1; i <= n; i++) {scanf("%lf%lf", &p[i].first, &p[i].second);}for (int i = 1; i <= n; i++) {scanf("%s", g[i] + 1);}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (g[i][j] == '1')d[i][j] = get_dist(p[i], p[j]);else if (i == j)d[i][j] = 0;else d[i][j] = INF;}}for (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {d[i][j] = min(d[i][j], d[i][k] + d[k][j]);}}}for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (d[i][j] < INF / 2)maxd[i] = max(maxd[i], d[i][j]);}}double ret1 = 0;for (int i = 1; i <= n; i++) {ret1 = max(ret1, maxd[i]);}double ret2 = INF;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if(d[i][j]>INF/2)ret2 = min(ret2, maxd[i] + maxd[j] + get_dist(p[i], p[j]));}}printf("%.6lf\n", max(ret1, ret2));return 0;
}
相关文章:

1125. 牛的旅行 (Floyd算法,最短路)
1125. 牛的旅行 - AcWing题库 农民John的农场里有很多牧区,有的路径连接一些特定的牧区。 一片所有连通的牧区称为一个牧场。 但是就目前而言,你能看到至少有两个牧区不连通。 现在,John想在农场里添加一条路径(注意ÿ…...
oracle “Interested Transaction List”(ITL)的概念
“Interested Transaction List”(ITL)的概念。让我们逐点理解: 块头和ITL: 每个数据库段块的块头都包含一个Interested Transaction List(ITL)。ITL用于确定数据库开始修改块时某个事务是否未提交。 ITL的…...

kali下-MSF-ftp_login模块破解FTP账号及密码
一、环境准备 两台设备在同一个网络内 一台kali系统:192.168.10.128 一台winserver2016:192.168.10.132 二、MSF介绍 metasploit 全称是The Metasploit Framework,又称MSF,是Kali 内置的一款渗透测试框架,也是全球…...

ELK之Filebeat输出日志格式设置及输出字段过滤和修改
一、Filebeat输出日志格式设置 1.1 编辑vim filebeat.yml文件,修改输出格式设置 # output to console output.console:codec.format: string: %{[@timestamp]} %{[message]}pretty: true### 1.2 测试 执行 ./filebeat -e 可以看到/tmp/access.log(目前文件里只有140.77.188…...

【开源】基于JAVA的河南软件客服系统
目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 系统管理人员2.2 业务操作人员 三、系统展示四、核心代码4.1 查询客户4.2 新增客户跟进情况4.3 查询客户历史4.4 新增服务派单4.5 新增客户服务费 五、免责说明 一、摘要 1.1 项目介绍 基于JAVAVueSpringBootMySQL的河…...

基于SpringBoot的社区帮扶对象管理系统
文章目录 项目介绍主要功能截图:部分代码展示设计总结项目获取方式 🍅 作者主页:超级无敌暴龙战士塔塔开 🍅 简介:Java领域优质创作者🏆、 简历模板、学习资料、面试题库【关注我,都给你】 &…...
uniapp踩坑之项目:canvas第一次保存是空白图片
在ctx.draw()回调生成图片,参考canvasToTempFilePath接口文档 // data imgFilePath: null,// 缓存二维码图片canvas路径//js // 首先在draw()里进行本地存储 ...... ctx.draw(false, () >{uni.canvasToTempFilePath({ // 把画布转化成临时…...
es-删除字段-实测
es字段一旦创建是无法删除的,本案的方案是复制新老索引的方法 一、背景 现有索引 index1,待删除字段field1和extendMap.field2,es版本6.3.2 二、步骤 1、删除index1中的filed1和extendMap.field2两个字段的数据 POST index1/_update_by_query {&qu…...
24秋招,百度测试开发工程师三面
前言 大家好,我是chowley,今天来回顾一下,我当时参加百度秋招补录,测试开发工程师的第三面-leader面 到面试开始的时间,面试官打电话表示让我等十分钟,随后跳过自我介绍,直接开面 时间&#…...
YOLOv8改进 | 主干篇 | 低照度增强网络PE-YOLO改进主干(改进暗光条件下的物体检测模型)
一、本文介绍 本文给大家带来的改进机制是低照度图像增强网络PE-YOLO中的PENet,PENet通过拉普拉斯金字塔将图像分解成多个分辨率的组件,增强图像细节和低频信息。它包括一个细节处理模块(DPM),用于通过上下文分支和边缘分支增强图像细节,以及一个低频增强滤波器(LEF),…...
【VUE】记录一次 VUE中配置生产环境和开发环境方法
前言 我这里 使用Vue CLI(Vue Command Line Interface)创建Vue.js项目是一种简单的方式,它提供了一个交互式的命令行工具来帮助你初始化和管理Vue.js项目。 并且我这个项目需要区分生产环境和开发环境。这里具体完整记录下,整个…...

tessreact训练字库
tessreact主要用于字符识别,除了使用软件自带的中英文识别库,还可以使用Tesseract OCR训练属于自己的字库。 一、软件环境搭建 使用Tesseract OCR训练自己的字库,需要安装Tesseract OCR和jTessBoxEditor(配套训练工具)。jTessBoxEditor需要…...
超时配置(OpenFeign)
默认值 连接超时,默认2s读取超时,默认5s单位: 毫秒 全局配置 package com.learning.springcloud.order.feign.config;import feign.Contract; import feign.Logger; import feign.Request; import org.springframework.context.annotation…...

C++设计模式(李建忠)笔记2
C设计模式(李建忠) 本文是学习笔记,如有侵权,请联系删除。 参考链接 Youtube: C设计模式 Gtihub源码与PPT:https://github.com/ZachL1/Bilibili-plus 豆瓣: 设计模式–可复用面向对象软件的基础 文章目录 C设计模…...
【机器学习】DBSCAN算法
参考链接: https://blog.csdn.net/haveanybody/article/details/113092851 https://www.jianshu.com/p/dd6ce77bfb8a 1 介绍 DBSCAN(Density-Based Spatial Clustering of Applica tion with Noise)算法是于1996年提出的一种简单的、有效的基于密度的聚类算法&…...

Uniapp软件库源码-全新带勋章等
测试环境:php7.1。ng1.2,MySQL 5.6 常见问题: 配置好登录后转圈圈,检查环境及伪静态以及后台创建好应用 上传图片不了,检查php拓展fileinfo 以及public文件权限 App个人主页随机背景图,在前端uitl文件夹里面…...

Microsoft Excel 直方图
Microsoft Excel 直方图 1. 数据示例2. 打开 EXCEL3. settings4. 单击直方图柱,右键“添加数据标签”References 1. 数据示例 2. 打开 EXCEL 数据 -> 数据分析 -> 直方图 3. settings 输入区域样本值、接受区域分类间距,输出选项选择“新工作表组…...

如何录制屏幕视频?让视频制作更简单!
随着数字化时代的来临,录制屏幕视频成为一种常见的传播和教学方式。无论是制作演示文稿、教学视频,还是记录游戏操作,屏幕录制为用户提供了强大而灵活的工具。可是您知道如何录制屏幕视频吗?本文将深入介绍两种常见的屏幕录制方法…...

【JavaEE进阶】 关于应用分层
文章目录 🎋序言🍃什么是应⽤分层🎍为什么需要应⽤分层🍀如何分层(三层架构)🎄MVC和三层架构的区别和联系🌳什么是高内聚低耦合⭕总结 🎋序言 在我们进行项目开发时我们如果一股脑将所有代码都…...

【已解决】c语言const/指针学习笔记
本博文源于笔者正在复习const在左与在右,指针优先级、a,&a,*a的区别。 1、const在左与在右 int const *p const int *p int * const p int const * const p const int * const p* 在const右边,指向的数据不可以改变,可以改变地址 * 在c…...
生成xcframework
打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式,可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

微信小程序之bind和catch
这两个呢,都是绑定事件用的,具体使用有些小区别。 官方文档: 事件冒泡处理不同 bind:绑定的事件会向上冒泡,即触发当前组件的事件后,还会继续触发父组件的相同事件。例如,有一个子视图绑定了b…...

关于nvm与node.js
1 安装nvm 安装过程中手动修改 nvm的安装路径, 以及修改 通过nvm安装node后正在使用的node的存放目录【这句话可能难以理解,但接着往下看你就了然了】 2 修改nvm中settings.txt文件配置 nvm安装成功后,通常在该文件中会出现以下配置&…...

前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...

tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
Device Mapper 机制
Device Mapper 机制详解 Device Mapper(简称 DM)是 Linux 内核中的一套通用块设备映射框架,为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程,并配以详细的…...

Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...