自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 23:18:14，当前版本为作者最后更新于2025-07-06 19:28:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

洛谷P12825 [NERC 2021] Labyrinth 题解

题外话

看到简单路径就有了大大滴思路，没想到调了两年半。。。

算法分析&介绍

不完全错误算法

千万别看到“路径”就只想到“最短路径”。首先题目说了 Leslie 和 Leon 的路径不必是最短路径，但必须是简单路径（即不重复访问任何大厅），就是说只要不怕麻烦，打个最短路径也是可以的 （能不能AC就不知道了）。

正确算法

由于是单向通道且没有环，我们可以考虑 BFS 树+祖先标记。

正确算法的步骤

1. BFS 遍历与祖先标记：从起点 $s$ 开始进行 BFS 遍历，记录每个节点的深度、父节点和祖先节点（从 $s$ 出发的第一条边指向的节点）。

2. 寻找汇合点：在 BFS 遍历过程中，对于每条边 $(u, v)$

• 如果 $v$ 未被访问，则正常入队，并记录其深度、父节点和祖先节点。
• 如果 $v$ 已被访问，且当前节点 $u$ 的祖先节点与 $v$ 的祖先节点不同，则找到满足条件的终点 $t = v$。

3. 路径重建：找到汇合点 t 后：

• 第一条路径：沿 BFS 树中 $t$ 到 $s$ 的路径重建。
• 第二条路径：沿 $t \to u \to s$ 的路径重建（$u$ 是发现汇合点时的当前节点）。

4. 无解情况：若 BFS 结束后未找到满足条件的汇合点，则输出 Impossible。

时间复杂度

$O(n+m)$，包过的。

AC Code

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0)，cout.tie(0);

    int n, m, s;
    cin >> n >> m >> s;
    vector<vector<int>> adj(n + 1);

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }

    vector<int> d(n + 1, -1);
    vector<int> p(n + 1, -1);
    vector<int> anc(n + 1, -1);
    queue<int> q;
    d[s] = 0;
    q.push(s);

    int t = -1, u_ = -1;

    while (!q.empty() && t == -1) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            if (v == s) continue;

            if (d[v] == -1) {
                d[v] = d[u] + 1;
                p[v] = u;
                if (u == s) anc[v] = v;
                else anc[v] = anc[u];
                q.push(v);
            } else {
                if (u == s) {
                    if (anc[v] != v) {
                        t = v;
                        u_ = u;
                        break;
                    }
                } else {
                    if (anc[u] != anc[v]) {
                        t = v;
                        u_ = u;
                        break;
                    }
                }
            }
        }
    }

    if (t == -1) {
        cout << "Impossible" << endl;
    } else {
        vector<int> p1;
        int cur = t;
        while (cur != s) {
            p1.push_back(cur);
            cur = p[cur];
        }
        p1.push_back(s);
        reverse(p1.begin(), p1.end());

        vector<int> p2;
        p2.push_back(t);
        if (u_ != s) {
            p2.push_back(u_);
            cur = u_;
            while (cur != s) {
                cur = p[cur];
                p2.push_back(cur);
            }
        } else {
            p2.push_back(s);
        }
        reverse(p2.begin(), p2.end());

        cout << "Possible" << endl;
        cout << p1.size() << endl;
        for (int i = 0; i < p1.size(); ++i) {
            if (i > 0) cout << " ";
            cout << p1[i];
        }
        cout << endl;

        cout << p2.size() << endl;
        for (int i = 0; i < p2.size(); ++i) {
            if (i > 0) cout << " ";
            cout << p2[i];
        }
        cout << endl;
    }

    return 0;
}

撒花！