题意
a,b 两点出发同一时刻最多移动一个单位。
a 是否可以追上 b?
题目分析
通过这道题,白嫖了一个新的知识点(虽然最后没用上)。
基环树:n个点n条边且保证联通则有且仅有一个环。
对于这道题目有一个核心策略为 在环中可以无限走下去。
因此,只要从 b 出发可以更快进入环 则 b 可以逃离。
整理一下:
1. 如果在同一个位置无法逃脱
2. 否则 如果在环内在可以一直躲避
3. 如果b在环外,求a到b最短路查看b是否能更快到达环
判断环内环外则使用拓扑排序,只要拓扑排序后度非零则为环上的点
b在环外
假设 L 为环中的点集,其中 $|L| = n$ ,并且有元素 $L_1,~L_2,~…,~L_{n},~L_i\in L$ 为环上的 一个点 。
则:
-
a到 $L_i$ 的距离为 $dist_{(a,L_i)}$ 记为 $dist_a$
-
b到 $L_i$ 的距离为 $dist_{(b,L_i)}$ 记为 $dist_b$
根据之前的策略则需要 $dist_a > dist_b$ ,则b更快到达环。
反证一下
由于移动速度相同,则a之前早已经追上b则存在一段d使得ab同时存在一个点上并向 $L_i$ 移动直至抵达。
因此,根据原式 $dist_a-d>dist_b-d$ ,由于移动速度相同,
所以 a 不可能追上b所以 如果 b 到 $L_i$ 的距离更短则一定可以逃离。
因此,只要满足 $\exists L_i =>dist_{(a,L_i)}>dist_{(b,L_i)} $ ,则一定可以逃离
所以本题拓扑排序+双次最短路(本题数据小一些直接求a和b的单源最短路)即可。
参考代码
#include<bits/stdc++.h>
using namespace std;
#define Maxn int(2e5+10)
#define head h
#define _to e[i].to
int d[Maxn];
int dist[Maxn],dist1[Maxn];
int fa[Maxn];
struct edge{
int next;
int to;
}e[Maxn<<1];
int h[Maxn];
int tot;
void add_edge(int u,int v);
int top(int n,int a,int b);
int cnt;
int main(){
int t;
cin>>t;
while(t--){
memset(h,0,sizeof h);
memset(d,0,sizeof d);
memset(dist,0x7f,sizeof dist);
memset(fa,0,sizeof dist);
memset(dist1,0x7f,sizeof dist1);
tot = 0;
int n,a,b;
cin>>n>>a>>b;
for(int i = 1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
add_edge(x,y);
add_edge(y,x);
}
if(top(n,a,b)){
cout<<"yes"<<endl;
}else{
cout<<"no"<<endl;
}
}
return 0;
}
void add_edge(int u,int v){
e[++tot].next = head[u];
head[u] = tot;
e[tot].to = v;
d[v]++;
}
int top(int n,int a,int b){
if(a==b)
return false;
queue<int> st;
for(int i = 1;i<=n;i++){
if(d[i]==1){
st.push(i);
}
}
while(st.size()){
int next = st.front();
st.pop();
d[next]--;
for(int i = head[next];i;i = e[i].next){
if(!d[e[i].to])
continue;
d[e[i].to]--;
if(d[e[i].to]==1){
st.push(e[i].to);
}
}
}
if(d[b]){
return true;
}
dist[a] = 0;
st = queue<int>();
st.push(a);
fa[a] = a;
while(st.size()){
int ne = st.front();
st.pop();
for(int i = head[ne];i;i = e[i].next){
int to = e[i].to;
if(dist[to]>dist[ne]+1){
dist[to] = dist[ne]+1;
fa[to] = ne;
st.push(to);
}
}
}
st.push(b);
dist1[b] = 0;
while(st.size()){
int ne = st.front();
st.pop();
for(int i = h[ne];i;i = e[i].next){
if(dist1[_to]>dist1[ne]+1){
dist1[_to] = dist1[ne]+1;
st.push(_to);
}
}
}
for(int i = 1;i<=n;i++){
if(!d[i]) continue;
if(dist[i]>dist1[i]){
return true;
}
}
return false;
}