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
https://img2024.cnblogs.com/blog/3481917/202407/3481917-20240717110025610-144683836.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
页:
[1]