1125. 牛的旅行
创始人
2025-05-30 20:18:11

Powered by:NEFU AB-IN

Link

文章目录

  • 1125. 牛的旅行
    • 题意
    • 思路
    • 代码

1125. 牛的旅行

  • 题意

    题目的问题：给定两个联通块，在两个连通块中各取任意一点进行连接合成一个连通块，求合并后的联通块的最长路径的最小值

  • 思路

    设 mximx_imxi​ 表示从i出发能到达的最长距离，设要连的边是(i, j)

    • 当 i,j 在同一连通块，答案就是∑mxi\sum mx_i∑mxi​
    • 当 i,j 在同一连通块，答案就是mxi+disi,j+mxjmx_i + dis_{i,j} + mx_jmxi​+disi,j​+mxj​

    用floyd算出任意两点的最短距离即可

  • 代码

    '''
Author: NEFU AB-IN
Date: 2023-03-19 15:48:41
FilePath: \Acwing\1125\1125.py
LastEditTime: 2023-03-19 16:27:41
'''
read = lambda: map(int, input().split())
from collections import Counter, deque
from heapq import heappop, heappush
from itertools import permutations
from math import sqrtN = int(160)
INF = int(2e9)
pos = [[] for _ in range(N)]
g = [0]
dist = [[INF] * N for _ in range(N)]
mx = [0] * Ndef cale(i, j):x1, y1 = pos[i]x2, y2 = pos[j]return sqrt(abs(x1 - x2)**2 + abs(y1 - y2)**2)def floyd():for k in range(1, n + 1):for i in range(1, n + 1):for j in range(1, n + 1):dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])n = int(input())
for i in range(1, n + 1):x, y = read()pos[i] = [x, y]for i in range(n):g.append('0' + input())for i in range(1, n + 1):for j in range(1, n + 1):if i == j:dist[i][j] = 0if g[i][j] == '1':dist[i][j] = dist[j][i] = cale(i, j)floyd()ans1, ans2 = 0, INF
for i in range(1, n + 1):for j in range(1, n + 1):if dist[i][j] != INF:mx[i] = max(mx[i], dist[i][j])ans1 = max(ans1, mx[i])for i in range(1, n + 1):for j in range(1, n + 1):if dist[i][j] == INF:ans2 = min(ans2, mx[i] + cale(i, j) + mx[j])print(f"{max(ans1, ans2):.6f}")
词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：js类型转换

下一篇：传输层协议之TCP协议详解

相关内容

热门资讯

GDPU C语言 天码行空3 1. 分段函数 #includeint main(){double x,y;scanf("%lf",...
【瑞萨 MCU】开发环境搭建之... e2 studio e2 studio（简称为 e2 或 e2s）是瑞萨...
C语言内联汇编 之前我们介绍了一种C语言与汇编代码混合编程方式，就是两个文件分开编写，分...
Linux 网络编程学习笔记—... 一、TCP 服务的特点 传输层协议主要有 TCP 协议和 UDP 协议，前者相对于后者...
KubeSphere All ... KubeSphere All in one安装配置手册 1. 初始化 1.1 配置apt源 # vi...
学习软件测试怎么能缺少练手的软... 你好，我是凡哥。 最近收到许多自学自动化测试的小伙伴私信，学习了理论知识...
【面试题】浅谈css加载是否会... 大厂面试题分享 面试题库前后端面试题库 （面试必备） 推荐：...
直播带货系统开发的关键点、代码... 时下，直播的热度依然不减，而它的产物之一：直播带货系统&#...
一文读懂强化学习！ 一.了解强化学习1.1基本概念强化学习是考虑智能体（Agent）与环境&...
Spring Cloud之一：... 目录 环境 Eureka工程的创建步骤 系列目录（持续更新。。。） S...
golang实现守护进程(2) 前言golang实现守护进程，包含功能：1. 守护进程只创建一次2. 平...
url 格式详解 统一资源定位系统（uniform resource locator; url ...
elasticsearch7.... elasticsearch版本：7.17.3 目标：实现对类型为text...
SpringBoot 加载系统... 开发环境: IDEA 2022.1.4+ MyBatis         代码参考:spri...
交换机概念和知识和命令 目录 一、华为交换机基础学习的一些重要概念和知识 二、交换机常用命令大全 三、不常用的交换机命令 ...
什么是 JavaScript ... 本文首发自「慕课网」，想了解更多IT干货内容，程序员圈内热闻࿰...
【C++】C++11——lam... 文章目录一、Lambda表达式引入二、Lambda表达式语法三、Lambda表达式交换两个值四、La...
Java分布式事务（十） 文章目录🔥分布式架构的理论知识_BASE理论🔥分布式事务解决方案_最...
vmware中centos7实... 前言 在开发收银系统SAAS版本时，采用的是centos服务器，经常需要...
计算机图形学 | 可编程渲染管... 计算机图形学 | 可编程渲染管线计算机图形学 | 可编程渲染管线3.1 从固定到可编程图形编程的发展...
linux下安装两个或多个to... 安装jdk，tomcat编辑环境变量profilevi /etc/profile加入以...
selenium的显示等待、隐... 关于selenium有三种等待方式，分别为显示等待、隐式等待、强制等待 1、强制等待 ...
测牛学堂：软件测试接口自动化之... requests库 用postman进行接口测试有一定的限制，我们测试更应该掌握的是用...
day36_jdbc 今日内容 上课同步视频:CuteN饕餮的个人空间_哔哩哔哩_bilibili 同步笔记沐沐霸的博客...
【java基础】Stream流... 文章目录基本介绍流的创建流的各种常见操作forEach方法filter方法map方法peek方法fl...
幂等性通用组件 一、什么是幂等性幂等是一个数学与计算机学概念，在数学中某一元运算为幂等时，...
Nacos服务注册 又是美好的一天呀~ 个人博客地址： huanghong.top 本文预估阅读时长为3...
令人惊艳的ChatGPT项目，... 自从 ChatGPT、Stable Diffusion 发布以来，各种相关开源项目百花...
舆情监测系统有哪些优势，TOO... 舆情监测系统是一种基于大数据技术的舆情分析工具，可以帮助企业、政府等机构实时监控公众对...
【Linux】基础IO流(上) 文章目录1. 预备知识2. 回忆C接口fopenfputsfprintfsnprintf追加方式——...