闹忧踫 发表于 2025-6-4 16:50:21

CodeForces Round 898 (div 4) H题解析

 

 
CodeForces Round 898 (div 4)
H. Mad  City

https://img2024.cnblogs.com/blog/3481917/202407/3481917-20240717105635429-1775658607.png
                                                    
大致思路     


[*]对于有n条边和n个点，说明这个图里面只有一个环
[*]并且两人同时开始和结束移动，所以可以得到当Valeriu进入到这个图里面的唯一的环里面时，Marcel就无法再抓到他，我们可以把离Valeriu最近的入环点叫做KeyPoint，所以我们就需要考虑Valeriu是否能在Marcel赶到KeyPoint之前赶到KeyPoint。
[*]所以找到入环点是这道题的切入点，找到入环点，我们就可以通过dfs暴搜来得出他们和入环点的距离来，通过比较来得出是否能够逃离。
Key：入环点的寻找

思路来源于洛谷的_Ink大佬
方法是通过拓扑，因为在拓扑的过程中，会一步步去删点删边，最后只剩下一个环。因为是要找离逃离者最近的入环点，所以我们可以把一开始的KeyPoint设为b点，即要逃离者所在地点，当 Keypoint 所在的点将被删时，由拓扑排序的特性，此时仅有一条边与其相连，所以我们可以在删这个点时顺势把KeyPoint 值更新到与被删点相连的那个点上。
由于拓扑排序不会删掉环上的点，所以当 KeyPoint 值不停更新，直到更新到环上的点时就不再发生变化。此时，KeyPoint 值就是我们想要的那个点的编号了。
这道题的图为无向图，所以拓扑过程中的删点删边条件应该为入度为1，这样环上的点就永远不会被删除。
完整代码

#include using namespace std;const int N = 200060, M = N > n >> a >> b;    init();    keypoint = b;    for(int i=1;i> u >> v;      add(u, v);      add(v, u);      to++;      to++;//因为是双向道路，所以两个点的入度都+1    }    for (int i = 1; i = 2 && a != b)//如果一开始b就在环上，而且a没有和b在同一栋大楼，就说明可以无期限逃    {      cout

左丘纨 发表于 2025-10-21 23:31:37

鼓励转贴优秀软件安全工具和文档！

颐港 发表于 2025-11-23 04:17:26

这个好，看起来很实用

靳夏萱 发表于 2025-12-21 10:48:11

收藏一下   不知道什么时候能用到

郏琼芳 发表于 2026-1-3 11:48:17

东西不错很实用谢谢分享

圣罩 发表于 2026-1-15 08:55:26

yyds。多谢分享

材部 发表于 2026-1-16 14:40:45

过来提前占个楼

孟清妍 发表于 2026-1-19 01:59:42

热心回复！

慢秤 发表于 2026-1-21 06:15:15

收藏一下   不知道什么时候能用到

采序 发表于 2026-1-21 16:16:14

很好很强大我过来先占个楼 待编辑

趣侮 发表于 2026-1-23 01:22:09

谢谢分享，辛苦了

钨哄魁 发表于 2026-1-23 04:30:07

感谢，下载保存了

巴沛若 发表于 2026-1-27 01:46:15

感谢分享，学习下。

梦霉 发表于 2026-2-4 10:15:37

收藏一下   不知道什么时候能用到

赴忽 发表于 2026-2-7 21:49:07

谢谢楼主提供！

蓬庄静 发表于 2026-2-8 03:03:16

鼓励转贴优秀软件安全工具和文档！

袁可佳 发表于 2026-2-8 13:34:07

谢谢分享，试用一下

求几少 发表于 2026-2-8 17:04:29

懂技术并乐意极积无私分享的人越来越少。珍惜

荪俗 发表于 2026-2-12 23:05:16

谢谢分享，辛苦了
页: [1]
查看完整版本: CodeForces Round 898 (div 4) H题解析