Mad City

题目大意

给定一个$n$个点，$n$条边的连通图。$A$从$a$点开始追赶处在$b$点的$B$，两人同时开始移动，并且$B$能准确预料到$A$下一步会去哪，并据此采取行动。问在两人都以最优策略开始移动的情况下，$A$是否永远都追不上$B$。

解题思路

$n$个点和$n$条边，意味着有且只有一个环。很明显$B$只要在走到环之前不被$A$截住的话就成功。分成以下几种情况：

  • $a==b$，直接输出$NO$;
  • $b$为环上的点，输出$YES$;
  • $b$不在环上，那么求一下环上离$B$最近的点到$A$，$B$的距离$dista$，$distb$，如果$dista<=distb$，说明$A$能在$B$赶到环上之前截住他，输出$NO$;反之，输出$YES$。

post_1

思路理清了，接下来考虑如何实现。

首先是判环，可以开一个$f$数组记录每个点的的前一个节点，初始化为$0$，然后进行$dfs$，在遍历到与当前点$x$相连的所有点时，如果碰到某个点$u$的$f[u]$不为$0$，则意味着碰到环了，使$f[u]=x$，然后就可以借助$f$数组求出环上的每个点。

环求出来之后就好办了，用$bfs$求一下距$B$最近的环上的点，再从这一点出发$bfs$求一下$dista$，$distb$即可。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
#define maxn 200100
#define int long long
using namespace std;
const double eps=1e-8;
vector<int>e[maxn];
int n,a,b,pre[maxn],dist[maxn];
bool ok,cyc[maxn],vis[maxn];
inline void dfs(int x,int fa){
    if(ok)  return ;
    pre[x]=fa;
    for(auto u:e[x]){
        if(u==fa)  continue;
        if(pre[u]){
            pre[u]=x;  cyc[u]=true;
            int t=u;
            while(1){
                t=pre[t];  cyc[t]=true;
                if(t==u){
                    ok=true;  return ;
                }
            }
        }
        dfs(u,x);
    }
}
void solve(){
    ok=false;
    cin >> n >> a >> b;
    for(int i=1;i<=n;++i)  e[i].clear(),cyc[i]=false,pre[i]=0,dist[i]=1e10,vis[i]=false;
    for(int i=1;i<=n;++i){
        int x,y;
        cin >> x >> y;
        e[x].push_back(y);  e[y].push_back(x);
    }
    dfs(1,-1);
    if(a==b)  {cout << "NO\n";return ;}
    if(cyc[b])  {cout << "YES\n";return ;}
    int pos=0;
    queue<int>q;
    q.push(b),vis[b]=true;
    while(q.size()&&!pos){
        int t=q.front();  q.pop();
        for(auto u:e[t]){
            if(vis[u])  continue;
            if(cyc[u])  {pos=u;break;}
            q.push(u);  vis[u]=true;
        }
    }
    while(q.size())  q.pop();
    q.push(pos);  dist[pos]=0;
    while(q.size()&&(dist[a]==1e10||dist[b]==1e10)){
        int t=q.front();  q.pop();
        for(auto u:e[t]){
            if(dist[u]!=1e10)  continue;
            dist[u]=min(dist[u],dist[t]+1);
            q.push(u);
        }
    }
    if(dist[a]<=dist[b])  cout << "NO\n";
    else  cout << "YES\n";
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t; cin >> t;
    while(t--){
        solve();
    }
    return 0;
}