当前位置: 首页 > news >正文

1125. 牛的旅行 (Floyd算法,最短路)

1125. 牛的旅行 - AcWing题库

农民John的农场里有很多牧区,有的路径连接一些特定的牧区。

一片所有连通的牧区称为一个牧场。

但是就目前而言,你能看到至少有两个牧区不连通。

现在,John想在农场里添加一条路径(注意,恰好一条)。

一个牧场的直径就是牧场中最远的两个牧区的距离(本题中所提到的所有距离指的都是最短的距离)。

考虑如下的两个牧场,每一个牧区都有自己的坐标:

1.png

图 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的农场里有很多牧区&#xff0c;有的路径连接一些特定的牧区。 一片所有连通的牧区称为一个牧场。 但是就目前而言&#xff0c;你能看到至少有两个牧区不连通。 现在&#xff0c;John想在农场里添加一条路径&#xff08;注意&#xff…...

oracle “Interested Transaction List”(ITL)的概念

“Interested Transaction List”&#xff08;ITL&#xff09;的概念。让我们逐点理解&#xff1a; 块头和ITL&#xff1a; 每个数据库段块的块头都包含一个Interested Transaction List&#xff08;ITL&#xff09;。ITL用于确定数据库开始修改块时某个事务是否未提交。 ITL的…...

kali下-MSF-ftp_login模块破解FTP账号及密码

一、环境准备 两台设备在同一个网络内 一台kali系统&#xff1a;192.168.10.128 一台winserver2016&#xff1a;192.168.10.132 二、MSF介绍 metasploit 全称是The Metasploit Framework&#xff0c;又称MSF&#xff0c;是Kali 内置的一款渗透测试框架&#xff0c;也是全球…...

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的社区帮扶对象管理系统

文章目录 项目介绍主要功能截图&#xff1a;部分代码展示设计总结项目获取方式 &#x1f345; 作者主页&#xff1a;超级无敌暴龙战士塔塔开 &#x1f345; 简介&#xff1a;Java领域优质创作者&#x1f3c6;、 简历模板、学习资料、面试题库【关注我&#xff0c;都给你】 &…...

uniapp踩坑之项目:canvas第一次保存是空白图片

在ctx.draw()回调生成图片&#xff0c;参考canvasToTempFilePath接口文档 // data imgFilePath: null,// 缓存二维码图片canvas路径//js // 首先在draw&#xff08;&#xff09;里进行本地存储 ...... ctx.draw(false, () >{uni.canvasToTempFilePath({ // 把画布转化成临时…...

es-删除字段-实测

es字段一旦创建是无法删除的&#xff0c;本案的方案是复制新老索引的方法 一、背景 现有索引 index1,待删除字段field1和extendMap.field2&#xff0c;es版本6.3.2 二、步骤 1、删除index1中的filed1和extendMap.field2两个字段的数据 POST index1/_update_by_query {&qu…...

24秋招,百度测试开发工程师三面

前言 大家好&#xff0c;我是chowley&#xff0c;今天来回顾一下&#xff0c;我当时参加百度秋招补录&#xff0c;测试开发工程师的第三面-leader面 到面试开始的时间&#xff0c;面试官打电话表示让我等十分钟&#xff0c;随后跳过自我介绍&#xff0c;直接开面 时间&#…...

YOLOv8改进 | 主干篇 | 低照度增强网络PE-YOLO改进主干(改进暗光条件下的物体检测模型)

一、本文介绍 本文给大家带来的改进机制是低照度图像增强网络PE-YOLO中的PENet,PENet通过拉普拉斯金字塔将图像分解成多个分辨率的组件,增强图像细节和低频信息。它包括一个细节处理模块(DPM),用于通过上下文分支和边缘分支增强图像细节,以及一个低频增强滤波器(LEF),…...

【VUE】记录一次 VUE中配置生产环境和开发环境方法

前言 我这里 使用Vue CLI&#xff08;Vue Command Line Interface&#xff09;创建Vue.js项目是一种简单的方式&#xff0c;它提供了一个交互式的命令行工具来帮助你初始化和管理Vue.js项目。 并且我这个项目需要区分生产环境和开发环境。这里具体完整记录下&#xff0c;整个…...

tessreact训练字库

tessreact主要用于字符识别&#xff0c;除了使用软件自带的中英文识别库&#xff0c;还可以使用Tesseract OCR训练属于自己的字库。 一、软件环境搭建 使用Tesseract OCR训练自己的字库&#xff0c;需要安装Tesseract OCR和jTessBoxEditor(配套训练工具)。jTessBoxEditor需要…...

超时配置(OpenFeign)

默认值 连接超时&#xff0c;默认2s读取超时&#xff0c;默认5s单位&#xff1a; 毫秒 全局配置 package com.learning.springcloud.order.feign.config;import feign.Contract; import feign.Logger; import feign.Request; import org.springframework.context.annotation…...

C++设计模式(李建忠)笔记2

C设计模式&#xff08;李建忠&#xff09; 本文是学习笔记&#xff0c;如有侵权&#xff0c;请联系删除。 参考链接 Youtube: C设计模式 Gtihub源码与PPT&#xff1a;https://github.com/ZachL1/Bilibili-plus 豆瓣: 设计模式–可复用面向对象软件的基础 文章目录 C设计模…...

【机器学习】DBSCAN算法

参考链接&#xff1a; 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软件库源码-全新带勋章等

测试环境&#xff1a;php7.1。ng1.2&#xff0c;MySQL 5.6 常见问题&#xff1a; 配置好登录后转圈圈&#xff0c;检查环境及伪静态以及后台创建好应用 上传图片不了&#xff0c;检查php拓展fileinfo 以及public文件权限 App个人主页随机背景图&#xff0c;在前端uitl文件夹里面…...

Microsoft Excel 直方图

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

如何录制屏幕视频?让视频制作更简单!

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

【JavaEE进阶】 关于应用分层

文章目录 &#x1f38b;序言&#x1f343;什么是应⽤分层&#x1f38d;为什么需要应⽤分层&#x1f340;如何分层(三层架构)&#x1f384;MVC和三层架构的区别和联系&#x1f333;什么是高内聚低耦合⭕总结 &#x1f38b;序言 在我们进行项目开发时我们如果一股脑将所有代码都…...

【已解决】c语言const/指针学习笔记

本博文源于笔者正在复习const在左与在右&#xff0c;指针优先级、a,&a,*a的区别。 1、const在左与在右 int const *p const int *p int * const p int const * const p const int * const p* 在const右边&#xff0c;指向的数据不可以改变&#xff0c;可以改变地址 * 在c…...

生成xcframework

打包 XCFramework 的方法 XCFramework 是苹果推出的一种多平台二进制分发格式&#xff0c;可以包含多个架构和平台的代码。打包 XCFramework 通常用于分发库或框架。 使用 Xcode 命令行工具打包 通过 xcodebuild 命令可以打包 XCFramework。确保项目已经配置好需要支持的平台…...

微信小程序之bind和catch

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

关于nvm与node.js

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

前端导出带有合并单元格的列表

// 导出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的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

css3笔记 (1) 自用

outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size&#xff1a;0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格&#xff…...

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

Linux --进程控制

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