LCP 21. 追逐游戏
题目大意
给定一棵 $N$ 个点的基环树（环套树）。给定图上两个起始位置 $A$ 和 $B$ ($A \neq B$)。每一轮 $A$ 先移动，$B$ 后移动。每次移动可以移动到图上当前点的相邻点或者保持不动。任意时刻如果 $A$ 和 $B$ 处在同一位置了，那么游戏结束。 $B$ 希望游戏尽量晚结束，而 $A$ 希望游戏尽量早结束。两个人都采取最优策略的情况下，输出结束时刻，如果不会永远不会结束输出 $-1$。
简要题解
首先注意到原题目中给的是一个 $N$ 个点 $N$ 个边的全联通图，那么也就是说这个特殊的图其实是一棵树加了一条边，也就是一个基环树或者说环套树。
这里我们先想树的情况，树是不会存在不会结束的情况的，简单的把 $A$ 作为根，此时你会发现每次 $A$ 只要向着 $B$ 所在的子树走就可以了，这样总会有一个时刻碰到 $B$。 $B$ 的走法也很简单，先尽量往上走，走到 $A$ 抓不到的位置，在这个过程中找一个离 $A$ 尽量远的位置走过去（对最初 $A$ 为根的树而言深度最大的点）。
接下来我们来考虑如果环存在的情况。我们发现如果 $B$ 能先于 $A$ 走到环上，如果 $B$ 走一格，$A$ 追一格的话就可以到天荒地老了。
！！！这里就是本题最大的坑点！如果环长度 $\ge 4$，这自然是没问题的，当 $A$ 也走到换上时，$B$ 只要根据 $A$ 的位置选择和自己的策略，即可永远保证 $A$ 在下一步无法抓到自己。但如果等于环长度是 $3$ 你会发现，这样就没法在环上永远的循环下去了，因为当 $A$，$B$ 都处于环上时，$B$ 无论怎么移动，要么 $B$ 装上 $A$，要么下一步 $A$ 都可以走到 $B$ 的位置。另外注意，图中没有重边自环，因此不会有 $\le 2$ 长的环。
想明白了这些之后剩下的就是一些技术问题和细节了。
问题一：如何找出图中的环？这个可以依赖于双联通分量算法，可以依赖于魔改有向图判环的算法（不推荐，容易写错细节），可以依赖于类似于拓扑排序的算法（依次删掉树的叶子，推荐）。
问题二：如何判断 $A$ 是否能早于 $B$ 到达环？
实际比赛的时候我写了另一种算法，就是从每个环上点为根去处理了每棵树上的节点及深度，祖先等信息。这样我只要找出 $A$ 到 $B$ 所在树的根的最短时间就可以了去和 $B$ 到根的时间对比就可以了。但是这种思路会非常难以处理环长为 $3$ 的情况，所以不推荐。
更好的方法是，可以对 $A$，$B$ 都进行 BFS 。假设 $A$，$B$ 到某点 i 的最短时间为 $da[i]$ 和 $db[i]$。我们会发现只要判断环上每个点是否存在满足 $da[i] > db[i] + 1$ 的情况就可以了。这里注意边界，如果 $da[i] = db[i] + 1$ 时，意味着 $B$ 走到某个位置时 $A$ 在下一步也可以走到，这是不符合无穷步数的条件的。只要环上任意有一点满足这个条件意味着，当 $B$ 走到环上对应位置时，$A$ 至少距离这个位置 $2$ 步，当下一步 $A$ 靠近过来时，$B$ 选择远离即可。相反情况的正确性我们考虑，$A$ 到环上所有点都比 $B$ “快”。考虑 $B$ 进环的位置，$A$ 只要来拦截这个位置即可。
问题三：当 $A$ 能追到 $B$ 时怎么输出距离呢？
我们发现由于 $B$ 可以等待，因此最终一定是 $A$ 走到 $B$ 的位置，而 $B$ 不会自投罗网少走一轮。此时我们会发现，如果不是起始时刻 $A$，$B$ 只有一步之遥的情况（需要特判），其他时候，$B$ 能移动到的位置也一定满足 $da[i] > db[i] + 1$ 这个关系。对于 $B$ 被截在树里的情况，这个关系是显然的，而最大步数也就是满足这个关系的最大的 $da[i]$显然走到这个点 $i$ 之前要么 $A$ 与 $B$ 走的是不同的路径，要么有一段重合路径，而重合路径上显然每一点都会满足不等式。
此时只剩下最后一个情况，就是 $3$ 长环，且 $A$ 不能阻止 $B$ 走进环的情况。也是这种情况下体现出了用 BFS 处理的优势。
考虑如下图的情况，此时 $B$ 是无法走入 $c$ 的子树的，而对于 $c$ 点的 $da[c] > db[c] + 1$ 判断是 $false$ 这也是没有问题的，而当 $B$ 走进环而 $A$ 在更远的位置时，对应判断是 $true$，意味着可以选择走进 $c$ 所在的树，和我们的预期一致。
|
a (A)
|
b
/ \
c --- d (B)
| |
当 $A$ 走到 $b$ 面临选择进 $c$ 或 $d$ 时，也不存在被 $B$ 先“骗”进某一分支而走更长路的情况，因为此时要么就是 $B$ 已经无处可走了，要么 $B$ 必然处于 $c$ 或 $d$ 的子树中，$A$ 走到对应的树的根 $c$ 或 $d$ 点即可，即 $A$ 总是在走最短路，而 $B$ 是否可达的最短路判断依旧有效，和之前的部分行为是一致的。
至此，这个题目得解。
复杂度
$T$：$O(N)$
$S$：$O(N)$
代码实现
我很怀疑这个题目的数据不够强（补题 AC 时也只有 55 个数据点），所以即使提交过了，也最好仔细思考下自己的提交对于所有的边界条件是否都有正确的处理，尤其是含有 $3$ 长环的情况。
class Solution {
public:
int INF=0x3f3f3f3f;
vector<vector<int> > g;
int n;
vector<int> deg;
vector<int> inloop;
void getloop()
{
inloop.assign(n,1);
queue<int> qu;
for(int i=0;i<n;i++)
if(deg[i]==1) qu.push(i);
while(!qu.empty())
{
int u=qu.front(); qu.pop();
inloop[u]=0;
for(int v:g[u])
{
if(--deg[v]==1)
qu.push(v);
}
}
}
vector<int> da,db;
void getdis(int st,vector<int> &d)
{
d.assign(n,INF);
queue<int> qu;
d[st]=0;
qu.push(st);
while(!qu.empty())
{
int u=qu.front(); qu.pop();
for(int v:g[u])
{
if(d[v]!=INF) continue;
d[v]=d[u]+1;
qu.push(v);
}
}
}
int chaseGame(vector<vector<int>>& edges, int startA, int startB) {
n=edges.size();
g.assign(n,vector<int>());
deg.assign(n,0);
startA--;
startB--;
for(auto e:edges)
{
int u=e[0]-1,v=e[1]-1;
if(u==startA&&v==startB || u==startB&&v==startA) return 1;
g[u].push_back(v);
g[v].push_back(u);
deg[u]++;
deg[v]++;
}
getloop();
getdis(startA,da);
getdis(startB,db);
int looplen=0;
for(int i=0;i<n;i++)
if(inloop[i]) looplen++;
if(looplen>3)
{
for(int i=0;i<n;i++)
if(inloop[i] && da[i] > db[i]+1) return -1;
}
int ans=0;
for(int i=0;i<n;i++)
if(da[i]>db[i]+1) ans=max(ans,da[i]);
return ans;
}
};
一点测试数据
比赛的时候卡在 $3$ 的问题上好久，自己手造了一些数据，可以试着用用。
[[1,2],[2,3],[3,4],[4,1],[2,5],[5,6]]
3
5
[[1,2],[2,3],[3,4],[4,1],[2,5],[5,6]]
3
5
[[1,2],[2,3],[3,4],[4,1],[2,5],[5,6]]
3
5
[[1,2],[2,3],[3,4],[4,5],[1,6],[1,7],[6,7]]
1
5
[[1,2],[2,3],[4,3],[3,5],[3,6],[5,6]]
1
4
[[1,2],[2,3],[3,4],[4,1]]
1
3
[[1,2],[2,3],[3,4],[4,1]]
2
4
[[1,2],[2,3],[3,4],[4,1]]
1
2
[[1,2],[2,3],[3,1],[1,4],[4,5],[1,6],[6,7]]
5
7
[[1,2],[2,3],[3,1],[1,4],[4,5],[1,6],[6,7]]
5
6
[[1,2],[2,3],[3,1],[1,4],[4,5],[1,6],[6,7],[5,8],[4,9],[9,10],[10,11]]
7
8
[[1,2],[2,3],[3,1],[1,4],[4,5],[1,6],[6,7],[5,8],[4,9],[9,10],[10,11],[7,12]]
12
8
[[1,2],[2,3],[3,4],[4,1]]
1
2
Next: [模板][数据结构] 二叉堆 Binary Heap