题解：P13001 [GCJ 2022 Finals] Wonderland Chase

· · 题解

这题只需要搞明白一件事情，剩下的就是一些很简单的图论操作了。

什么时候追不到，能跑掉呢？很显然 10^9 的次数意思是告诉我们永远都追不上才能跑掉。只有两种情况符合这种要求：

  1. Alice 与红心皇后不在一个连通块，这样皇后无论如何也跑步过来。
  2. Alice 能赶在被抓伤之前跑进一个环。因为一旦在环里面，Alice 无论如何都有一条路可以走。

否则，Alice 一定就会被追上。这时只需要找到一个点，使得Alice 能在皇后赶到之前抵达，最大化皇后赶到的时间即可。

实现起来的话，先标记所有处于环内的点。由于这是无向图，我们不用什么 tarjan 之类的算法，只需要依次移除所有度为 1 的点即可。

接下来就是跑两次 dijkstra，记录所有点距离皇后与 Alice 分别有多远，然后遍历所有点。若点处于环内，且距离 Alice 比距离皇后近，则代表 Alice 安全。否则若不在环但仍然离 Alice 更近，则更新一下答案。若皇后距离 Alice 所在的点为无穷大，则 Alice 也是安全的。

最后注意乘以 2，因为皇后动一步 Alice 也得动一步。

以下代码是处理每一个测试点的代码，注意多测清空。

cin>>j>>c>>a>>q;
while (c--){
    int u,v;
    cin>>u>>v;
    adj[u].push_back(v);
    adj[v].push_back(u);
    deg[u]++;
    deg[v]++;
}
for (int i=1;i<=j;i++) alice[i]=queen[i]=MAXN; 
queue<pair<int,int>> qq;
qq.push({0,a});
while (qq.size()){
    auto qf=qq.front();
    qq.pop();
    if (alice[qf.second]!=MAXN) continue;
    alice[qf.second]=qf.first;
    for (int i:adj[qf.second]) qq.push({qf.first+1,i});
}
qq.push({0,q});
while (qq.size()){
    auto qf=qq.front();
    qq.pop();
    if (queen[qf.second]!=MAXN) continue;
    queen[qf.second]=qf.first;
    for (int i:adj[qf.second]) qq.push({qf.first+1,i});
}
for (int i=1;i<=j;i++) cycle[i]=1;
queue<int> qqq;
for (int i=1;i<=j;i++){
    if (deg[i]==1) {
        qqq.push(i);
    }
}
while (qqq.size()){
    int qf=qqq.front();
    qqq.pop();
    vis[qf]=1;
    cycle[qf]=0;
    for (int i:adj[qf]) {
        if (!vis[i]) {
            deg[i]--;
            if (deg[i]==1) qqq.push(i);
        }
    }
}

int ans=0;
for (int i=1;i<=j;i++){
    if (alice[i]==MAXN) continue;
    if (alice[i]<queen[i]) ans=max(ans,queen[i]);
    if ((cycle[i]&&alice[i]<queen[i])||(alice[i]!=MAXN&&queen[i]==MAXN)){
        cout<<"SAFE\n";
        return ;
    }
}
cout<<ans*2<<"\n";