H. Mad City
题目链接:Problem - H - Codeforces
题目大意:给定一个带环的图, 以及a, b两点 判断再图上不断的移动, b想不与a相遇, a想捉到b, 并且二者只能移动一步。 若b跑不掉 NO 否则YES.
具体题目看链接
输入:
第一行包含一个整数 t (1≤t≤1000 ) - 测试用例数。
每个测试用例的第一行包含三个空格分隔的整数 n , a , b ( 3≤n≤2⋅1e5 ;( 3≤n≤2⋅1e5 ; 1≤a,b≤n )--
下面的 n 行分别包含两个整数 ui , vi .( 1≤ui,vi≤n, ui≠vi )-- ui 和 vi 之间有一条道路。
所有测试用例中 n 的总和不超过 2⋅1e5 。
保证有环.
解题思路: 通过题目信息, 判断两个点是否肯定会相遇
1.若两个点在环上,那么一定不会相遇,可直接输出YES.
2.该题考察基环树, 当b不在环上时,那么若a点还想与b点相遇, 只有在b点未进入环时堵住b进入环的入环点。所以判断b点到进入环的入点的距离 与 入环点到a点的距离,设入环点为p点。 则需判断 pa <= pb 是NO, 否则 YES.
3.做法, 由于基环树, 要用到拓朴排序, 去掉枝丫, 先判断b点是否在环里。 若不在,则需要做dfs, 搜索出pa, pb的距离。 而p点的求法, 在拓朴排序是删掉该点p时就更新p点的下一个点为p.机p == u 时, p = v.即可找出在环上离b点最近的点p.
#include<bits/stdc++.h>
using namespace std;using i64 = long long;
using i128 = __int128;void solve(){int n, a, b;cin >> n >> a >> b;vector<int> d(n+1);vector<vector<int>> g(n+1);for(int i=0; i<n; i++) {int u, v;cin >> u >> v;d[u]++, d[v]++;g[u].push_back(v);g[v].push_back(u);}if(a==b){//特判cout << "NO\n";return;}queue<int> q;int p = b;for(int i=1; i<=n; i++) {if(d[i]==1) {q.push(i);}}//拓朴排序找里b点最近的环上点while(!q.empty()) {int u = q.front();q.pop();d[u]--;for(int v : g[u]) {if(d[v]==0)continue;d[v]--;if(d[v]==1) {q.push(v);}if(u==p) {//删点时不断靠近环p = v;}}}set<int> st;for(int i=1; i<=n; i++) {if(d[i] >= 2) {st.insert(i);}}//判断b是否再环上if(st.contains(b)) {cout << "YES\n";return;}int dis1 = INT_MAX/2, dis2 = INT_MAX/2;vector<int> vis(n+1,0);//dfs搜索距离auto dfs = [&](auto&&dfs, int u,int len)->void{if(u==a || u==b){if(u==a) {dis1 = min(len, dis1);}if(u==b) {dis2 = min(len, dis2);}return;}vis[u] = 1; for(int v : g[u]) {if(vis[v]==0) {dfs(dfs, v, len+1);}}vis[u] = 0;//再图上搜索,记得回溯};dfs(dfs, p, 0);if(dis1 <= dis2) {//最后的判断cout << "NO\n";}else{cout << "YES\n";}
}int main(){ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t;cin >> t;while(t--) {solve();}
}
欢迎各位点赞与观看, 欢迎大佬指正。
相关文章:
H. Mad City
题目链接:Problem - H - Codeforces 题目大意:给定一个带环的图, 以及a, b两点 判断再图上不断的移动, b想不与a相遇, a想捉到b, 并且二者只能移动一步。 若b跑不掉 NO 否则YES. 具体题目看链接 输入: …...

【图床配置】PicGO+Gitee方案
【图床配置】PicGOGitee方案 文章目录 【图床配置】PicGOGitee方案为啥要用图床图床是什么配置步骤下载安装PicGoPicGo配置创建Gitee仓库Typora中的设置 为啥要用图床 在Markdown中,图片默认是以路径的形式存在的,类似这样 可以看到这是本地路径&#x…...
《程序人生》工作2年感悟
一些杂七杂八的感悟: 1.把事做好比什么都重要, 先树立量良好的形象,再横向发展。 2.职场就是人情世故,但也不要被人情世故绑架。 3.要常怀感恩的心,要记住帮助过你的人,愿意和你分享的人,有能力…...
当当网近30日热销图书的数据采集与可视化分析(scrapy+openpyxl+matplotlib)
当当网近30日热销图书的数据采集与可视化分析(scrapy+openpyxl+matplotlib) 当当网近30日热销书籍官网写在前面 实验目的:实现当当网近30日热销图书的数据采集与可视化分析。 电脑系统:Windows 使用软件:Visual Studio Code Python版本:python 3.12.4 技术需求:scrapy、…...

unity学习25:用 transform 进行旋转和移动,简单的太阳地球月亮模型,以及父子级关系
目录 备注内容 1游戏物体的父子级关系 1.1 父子物体 1.2 坐标关系 1.3 父子物体实际是用 每个gameobject的tranform来关联的 2 获取gameObject的静态数据 2.1 具体命令 2.2 具体代码 2.3 输出结果 3 获取gameObject 的方向 3.1 游戏里默认的3个方向 3.2 获取方向代…...
【项目集成Husky】
项目集成Husky 安装初始化 Husky在.husky → pre-commit文件中添加想要执行的命令 安装 使用 Husky 可以帮助你在 Git 钩子中运行脚本,例如在提交代码前运行测试或格式化代码pnpm add --save-dev husky初始化 Husky npx husky init这会在项目根目录下创建一个 .hu…...

基于Spring Security 6的OAuth2 系列之七 - 授权服务器--自定义数据库客户端信息
之所以想写这一系列,是因为之前工作过程中使用Spring Security OAuth2搭建了网关和授权服务器,但当时基于spring-boot 2.3.x,其默认的Spring Security是5.3.x。之后新项目升级到了spring-boot 3.3.0,结果一看Spring Security也升级…...

【Matlab高端绘图SCI绘图模板】第006期 对比绘柱状图 (只需替换数据)
1. 简介 柱状图作为科研论文中常用的实验结果对比图,本文采用了3组实验对比的效果展示图,代码已调试好,只需替换数据即可生成相关柱状图,为科研加分。通过获得Nature配色的柱状图,让你的论文看起来档次更高࿰…...

Java 大视界 -- Java 大数据在生物信息学中的应用与挑战(67)
💖亲爱的朋友们,热烈欢迎来到 青云交的博客!能与诸位在此相逢,我倍感荣幸。在这飞速更迭的时代,我们都渴望一方心灵净土,而 我的博客 正是这样温暖的所在。这里为你呈上趣味与实用兼具的知识,也…...
.NET Core 中依赖注入的使用
ASP.NET Core中服务注入的地方 在ASP.NET Core项目中一般不需要自己创建ServiceCollection、IServiceProvider。在Program.cs的builder.Build()之前向builder.Services中注入。在Controller中可以通过构造方法注入服务。 低使用频率的服务 把Action用到的服务通过Action的参…...
deepseek 潜在变量Z的计算;变分自编码器(VAE); 高斯混合模型(GMM)
潜在注意力:潜在变量 Z Z Z的计算 潜在变量 Z Z Z...
rsync安装与使用-linux015
使用 rsync 可以非常高效地将文件或目录从一个服务器传输到另一个服务器。 能力: 支持 64 位文件、64 位 inode、64 位时间戳、64 位长整型支持套接字对、符号链接、符号链接时间、硬链接、硬链接特殊文件、硬链接符号链接支持 IPv6、访问时间(atimes&…...
CAP 定理的 P 是什么
分布式系统 CAP 定理 P 代表什么含义 作者之前在看 CAP 定理时抱有很大的疑惑,CAP 定理的定义是指在分布式系统中三者只能满足其二,也就是存在分布式 CA 系统的。作者在网络上查阅了很多关于 CAP 文章,虽然这些文章对于 P 的解释五花八门&am…...
【multi-agent-system】ubuntu24.04 安装uv python包管理器及安装依赖
uv包管理器是跨平台的 参考sudo apt-get update sudo apt-get install -y build-essential我的开发环境是ubuntu24.04 (base) root@k8s-master-pfsrv:/home/zhangbin/perfwork/01_ai/08_multi-agent-system# uv venv 找不到命令 “uv”,但可以通过以下软件...
JavaScript原型链与继承:优化与扩展的深度探索
在 JavaScript 的世界里,万物皆对象,而每个对象都有一个与之关联的原型对象,这就构成了原型链的基础。原型链,简单来说,是一个由对象的原型相互连接形成的链式结构 。每个对象都有一个内部属性[[Prototype]]࿰…...
5 长度和距离计算模块(length.rs)
这段代码定义了一个泛型结构体 Length<T, Unit>,用于表示一维长度,其中 T 表示长度的数值类型,而 Unit 是一个编译时检查单位一致性的占位符类型,不会用于运行时表示长度的值。这个设计允许开发者在编译阶段确保不同单位之间…...

ollama改模型的存盘目录解决下载大模型报c:盘空间不足的问题
使用Ollama和Open WebUI快速玩转大模型:简单快捷的尝试各种llm大模型,比如DeepSeek r1,非常简单方便,参见:使用Ollama和Open WebUI快速玩转大模型:简单快捷的尝试各种llm大模型,比如DeepSeek r1…...
OSCP:常见文件传输方法
在渗透测试过程中,文件传输是一个关键环节,涉及不同的协议和工具,本文整理了 Linux 和 Windows 系统下常见的文件传输方法,并提供相应的命令示例。 通用文件传输方式 Base64 编码传输 Base64 可用于跨平台传输文件,…...

B站吴恩达机器学习笔记
机器学习视频地址: 4.5 线性回归中的梯度下降_哔哩哔哩_bilibili 机器学习分类: 1. 有监督学习(Supervised Learning) 在有监督学习中,训练数据包含了输入特征和正确的输出标签,模型通过这些带有标签的…...
Java 性能优化与新特性
Java学习资料 Java学习资料 Java学习资料 一、引言 Java 作为一门广泛应用于企业级开发、移动应用、大数据等多个领域的编程语言,其性能和特性一直是开发者关注的重点。随着软件系统的规模和复杂度不断增加,对 Java 程序性能的要求也越来越高。同时&a…...

idea大量爆红问题解决
问题描述 在学习和工作中,idea是程序员不可缺少的一个工具,但是突然在有些时候就会出现大量爆红的问题,发现无法跳转,无论是关机重启或者是替换root都无法解决 就是如上所展示的问题,但是程序依然可以启动。 问题解决…...

Linux 文件类型,目录与路径,文件与目录管理
文件类型 后面的字符表示文件类型标志 普通文件:-(纯文本文件,二进制文件,数据格式文件) 如文本文件、图片、程序文件等。 目录文件:d(directory) 用来存放其他文件或子目录。 设备…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...

零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...

面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)
考察一般的三次多项式,以r为参数: p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]; 此多项式的根为: 尽管看起来这个多项式是特殊的,其实一般的三次多项式都是可以通过线性变换化为这个形式…...
深度学习之模型压缩三驾马车:模型剪枝、模型量化、知识蒸馏
一、引言 在深度学习中,我们训练出的神经网络往往非常庞大(比如像 ResNet、YOLOv8、Vision Transformer),虽然精度很高,但“太重”了,运行起来很慢,占用内存大,不适合部署到手机、摄…...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道
文/法律实务观察组 在债务重组领域,专业机构的核心价值不仅在于减轻债务数字,更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明,合法债务优化需同步实现三重平衡: 法律刚性(债…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能
指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...

解析两阶段提交与三阶段提交的核心差异及MySQL实现方案
引言 在分布式系统的事务处理中,如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议(2PC)通过准备阶段与提交阶段的协调机制,以同步决策模式确保事务原子性。其改进版本三阶段提交协议(3PC…...