CodeForces Round 898 (div 4) H题解析
CodeForces Round 898 (div 4)
H. Mad City
大致思路
- 对于有n条边和n个点,说明这个图里面只有一个环
- 并且两人同时开始和结束移动,所以可以得到当Valeriu进入到这个图里面的唯一的环里面时,Marcel就无法再抓到他,我们可以把离Valeriu最近的入环点叫做KeyPoint,所以我们就需要考虑Valeriu是否能在Marcel赶到KeyPoint之前赶到KeyPoint。
- 所以找到入环点是这道题的切入点,找到入环点,我们就可以通过dfs暴搜来得出他们和入环点的距离来,通过比较来得出是否能够逃离。
Key:入环点的寻找
思路来源于洛谷的_Ink大佬
方法是通过拓扑,因为在拓扑的过程中,会一步步去删点删边,最后只剩下一个环。因为是要找离逃离者最近的入环点,所以我们可以把一开始的KeyPoint设为b点,即要逃离者所在地点,当 Keypoint 所在的点将被删时,由拓扑排序的特性,此时仅有一条边与其相连,所以我们可以在删这个点时顺势把KeyPoint 值更新到与被删点相连的那个点上。
由于拓扑排序不会删掉环上的点,所以当 KeyPoint 值不停更新,直到更新到环上的点时就不再发生变化。此时,KeyPoint 值就是我们想要的那个点的编号了。
这道题的图为无向图,所以拓扑过程中的删点删边条件应该为入度为1,这样环上的点就永远不会被删除。
完整代码
#include <bits/stdc++.h>
using namespace std;
const int N = 200060, M = N << 1;
int h[N], ne[M], e[M], idx;
int n, a, b, keypoint;
int to[N];//记录一个点的入度
bool vist[N], st[N];
int dista, distb;//记录a,b离关键点的距离
void add(int a, int b)//链式前向星式建图
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void topsort(int dot)//对入度为1的点进行拓扑
{
vist[dot] = true;//把这个点标记,表示在此次拓扑中已经被访问
for (int i = h[dot]; ~i; i = ne[i])
{
int j = e[i];
if (vist[j] || to[j]==0)continue;//如果这个点已经被访问过,就跳过
//如果这个点已经被删除也跳过
to[dot]--;
to[j]--;//因为是双向的道路,删边需要两个点的入度都减1
if (dot == keypoint)keypoint = j;//删点,如果这个点是关键点就转移关键点
if (to[j] == 1)topsort(j);//对于入度为1的点进行拓扑
}
vist[dot] = false;//恢复状态
}
void dfs(int x, int dist)//dfs暴搜求a和b到关键点的距离
{
st[x] = true;//标记点已经访问
if (x == a)dista = min(dista, dist);
if (x == b)distb = min(distb, dist);
for (int i = h[x]; ~i; i = ne[i])
{
int j = e[i];
if (st[j])continue;//如果点已经被访问就跳过
dfs(j, dist + 1);
}
st[x] = false;//恢复现场
}
void init()//对于每一次的状态的初始化
{
memset(h, -1, sizeof h);
idx = 0;
memset(to, 0, sizeof to);
memset(st, 0, sizeof st);
memset(vist, 0, sizeof vist);
dista = distb = 0x3f3f3f3f;
}
void solve()
{
cin >> n >> a >> b;
init();
keypoint = b;
for(int i=1;i<=n;i++)
{
int u, v;
cin >> u >> v;
add(u, v);
add(v, u);
to[u]++;
to[v]++;//因为是双向道路,所以两个点的入度都+1
}
for (int i = 1; i <= n; i++)if (to[i] == 1)topsort(i);
//找到入度为1的点进行拓扑
if (to[b] >= 2 && a != b)//如果一开始b就在环上,而且a没有和b在同一栋大楼,就说明可以无期限逃
{
cout << "YES" << endl;
return;
}
else if (a == b) {//如果a和b在同一栋大楼,就直接被抓了
cout << "NO" << endl;
return;
}
dfs(keypoint, 0);//DFS查找a和b两点离关键点的距离
//如果a到关键点的距离大于b到关键点的距离,说明b可以比a先到环上,所以可以无期限逃,反之不可以
if (dista > distb)cout << "YES" << endl;
else cout << "NO" << endl;
}
int main()
{
int t;
cin >> t;
while (t--)
{
solve();
}
return 0;
}
热门相关:大唐第一世家 隐婚101天:唐少宠妻成瘾 脑洞大爆炸 汉阙 超级融合