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…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...
【Go语言基础【13】】函数、闭包、方法
文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数(函数作为参数、返回值) 三、匿名函数与闭包1. 匿名函数(Lambda函…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖
在Vuzix M400 AR智能眼镜的助力下,卢森堡罗伯特舒曼医院(the Robert Schuman Hospitals, HRS)凭借在无菌制剂生产流程中引入增强现实技术(AR)创新项目,荣获了2024年6月7日由卢森堡医院药剂师协会࿰…...

逻辑回归暴力训练预测金融欺诈
简述 「使用逻辑回归暴力预测金融欺诈,并不断增加特征维度持续测试」的做法,体现了一种逐步建模与迭代验证的实验思路,在金融欺诈检测中非常有价值,本文作为一篇回顾性记录了早年间公司给某行做反欺诈预测用到的技术和思路。百度…...

(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

DBLP数据库是什么?
DBLP(Digital Bibliography & Library Project)Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高,数据库文献更新速度很快,很好地反映了国际计算机科学学术研…...
OCC笔记:TDF_Label中有多个相同类型属性
注:OCCT版本:7.9.1 TDF_Label中有多个相同类型的属性的方案 OCAF imposes the restriction that only one attribute type may be allocated to one label. It is necessary to take into account the design of the application data tree. For exampl…...

【图片转AR场景】Tripo + Blender + Kivicube 实现图片转 AR 建模
总览 1.将 2D 图片转为立体建模 2. 3. 一、将 2D 图片转为立体建模 1.工具介绍 Tripo 网站 2.找图片 找的图片必须是看起来能够让 AI 有能力识别和推理的,因为现在的AI虽然可以补全但是能力还没有像人的想象力那么丰富。 比如上面这张图片,看起来虽…...
C#调用Rust动态链接库DLL的案例
C#调用Rust动态链接库DLL的案例 项目概述 这是一个演示C#调用Rust动态链接库DLL的项目,包含: C#主程序 (Program.cs)Rust动态链接库 (rust_to_csharp目录) 使用C#创建一个net9的控制台项目,不使用顶级语句 dotnet new console --framewo…...