「COCI 2023.1」Skrivača 题解

题目大意

这是一个在连通无向图上进行的双人游戏：

• Marin 从某个起始房间 $v_0$ 开始
• Luka 根据策略函数 $a$ 选择藏身位置：当 Marin 在房间 $v$ 时，Luka 藏在 $a_v$
• 每轮 Marin 移动到相邻房间，然后 Luka 可以沿任意路径移动到新的藏身位置 $a_u$
• 当两人在同一房间时游戏结束
• 求从每个房间开始时，Marin 在双方最优策略下的最少捕获轮数

解题思路

关键观察

1. 立即捕获情况：

   • 如果 $a_i = i$，Marin 一开始就发现 Luka（轮数 = 0）
   • 如果存在边 $(u,v)$ 且 $a_u = v$，Marin 一步就能发现 Luka

2. 图论性质：

   • 使用 DFS 树和 Tarjan 算法找割点
   • 分析双连通分量结构

3. 多源 BFS：

   • 从已知轮数的位置开始扩展
   • 逐步计算其他位置的轮数

代码解析

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = (a), stOwrh = (b); i <= stOwrh; i++)
#define per(i, a, b) for(int i = (a), stOwrh = (b); i >= stOwrh; i--)
using namespace std;
using LL = long long;
using VI = vector<int>;
template<int siz> using AI = array<int, siz>;

constexpr int N = 2e5 + 5;

int n, m;
int ans[N], A[N];        // ans[i]: 从房间i开始的最少轮数, A[i]: 策略函数
vector<int> adj[N];      // 邻接表
queue<int> q;            // BFS队列

// Tarjan算法相关变量
int dfn[N], low[N];

// DFS遍历，识别割点和双连通分量
void dfs(int u, int pa) {
    dfn[u] = low[u] = ++dfn[N - 1];  // 时间戳
    int tg = dfn[A[u]] ? -1 : -2;    // 目标标记
    vector<AI<2>> vec;               // 存储子树信息

    for (auto v : adj[u])
        if (v != pa) {
            if (dfn[v] == 0) {
                dfs(v, u);
                
                // 判断u是否为割点
                if (low[v] >= dfn[u])
                    vec.push_back({dfn[v], dfn[N - 1]});
                
                // 更新目标标记
                if (tg == -2 && dfn[A[u]]) {
                    if (low[v] >= dfn[u])
                        tg = (int)vec.size() - 1;
                    else
                        tg = -1;
                }
                
                low[u] = min(low[u], low[v]);
            } else {
                low[u] = min(low[u], dfn[v]);
            }
        }

    if (vec.empty()) return;

    tg = max(tg, -1);

    // 检查邻居节点是否可以一步捕获
    for (auto v : adj[u]) {
        int it = prev(lower_bound(vec.begin(), vec.end(), 
                     AI<2> {dfn[A[v]], INT_MAX})) - vec.begin();
        
        if (it != -1 && vec[it][1] < dfn[A[v]])
            it = -1;
        
        // 如果可以一步捕获，加入BFS队列
        if (it != tg && ans[v] == INT_MAX)
            q.push(v), ans[v] = 1;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    fill(ans, ans + 1 + n, INT_MAX);  // 初始化答案为无穷大
    rep(i, 1, n) cin >> A[i];         // 读入策略函数

    // 建图
    for (int i = 1, u, v; i <= m; i++)
        cin >> u >> v, adj[u].emplace_back(v), adj[v].emplace_back(u);

    // 情况1: 起始位置直接捕获 (a_i = i)
    rep(i, 1, n) if (A[i] == i)
        ans[i] = 0, q.emplace(i);

    // 情况2: 一步捕获 (存在边(u,v)且a_u = v)
    rep(u, 1, n) {
        for (auto v : adj[u])
            if (v == A[u] && ans[u] == INT_MAX)
                ans[u] = 1, q.emplace(u);
    }

    // DFS分析图结构，找出更多一步捕获的情况
    dfs(1, 0);

    // 多源BFS扩展，计算其他位置的轮数
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        for (auto v : adj[u])
            if (ans[u] + 1 < ans[v]) {
                q.push(v);
                ans[v] = ans[u] + 1;
            }
    }

    // 输出结果，无法捕获的输出-1
    rep(i, 1, n) cout << (ans[i] >= INT_MAX ? -1 : ans[i]) << " \n"[i == n];

    return 0;
}

算法正确性

为什么这样设计？

1. 初始情况处理：

   • 直接捕获（轮数 = 0）：$a_i = i$
   • 一步捕获（轮数 = 1）：存在边 $(u,v)$ 且 $a_u = v$

2. DFS 分析：

   • 识别割点和双连通分量
   • 分析 Luka 的移动路径是否会被 Marin 截获
   • 找出更多一步捕获的机会

3. BFS 扩展：

   • 从已知轮数的位置开始
   • 逐步计算更远位置的轮数
   • 保证找到最短路径

复杂度分析

• 时间复杂度：$O(n + m)$
  • DFS: $O(n + m)$
  • BFS: $O(n + m)$
• 空间复杂度：$O(n + m)$

样例验证

样例1

输入：
4 4
3 4 1 2
1 2
2 3
3 4
4 1
输出：
-1 -1 -1 -1

所有起始位置都无法捕获 Luka，因为形成了循环。

样例2

输入：
8 9
2 3 2 1 6 5 6 7
...
输出：
1 2 2 2 1 1 1 1

符合题目描述的最优策略。

总结

本题的巧妙解法在于：

1. 分层处理：先处理简单情况，再分析复杂情况
2. 图论分析：利用割点和双连通分量识别关键位置
3. 多源 BFS：高效计算所有起始位置的最优解

这种结合图论分析和 BFS 扩展的方法，对于解决图上的博弈问题具有很好的参考价值。