Znzryb's Blog
0%

2025-沈阳站-区域赛-F. The Bond Beyond Time（友谊天长地久）（如何使用 bfs 找一个无弦环）（这种题目，我感觉啊，想要做出来的话，要么就是你的思路得比较好，要么就是还是得写个对拍）

Posted on Edited on

题目大意

"
Sulfox the fennec fox已经建立了一个迷宫，并邀请他的两个朋友Alice和Bob来尝试。迷宫可以抽象为一个简单的、连通的无向图，其中有nn个顶点和mm条边，Alice和Bob在两个指定的不同顶点开始。

在任何玩家移动之前，Sulfox必须为每条无向边选择一个方向，将迷宫变成一个有向图。然后，为了找到对方，两位玩家在定向迷宫内进行回合移动。在每一轮中，他们同时独立行动，不留下任何标记或沟通；相反，他们采取“最愚蠢”的策略：

  • 如果玩家当前位于一个具有一个或多个出边的顶点，则他们会任意穿越一个出边到相邻顶点；

  • 否则，如果他们当前的顶点没有出边，则他们将停留在该顶点。

作为对自己迷宫设计技能感到自豪的Sulfox，希望将通道定向，以便Alice和Bob永远不会相遇。鉴于无向图和Alice和Bob的起始顶点，请帮助Sulfox定向每条边，使得无论Alice和Bob如何在每一轮中做出选择，他们永远不会在任何一轮结束时占据同一顶点。如果不存在这样的定向，请报告。"

思路讲解

我记得是这样子的，只要两个玩家所在顶点不直接相连，就简单了，所有连着两个点的边全部指向这两点，可以把这两个玩家封死。

两个玩家所在顶点直接相连，就找最小的环，所有其他点（边）指向这个环，避免两个玩家离开这个环。

我们需要两次 bfs 实现：

这一部分 bfs 实现，负责这个找到包含 X→YX → Y 的环（这个相对容易），如果知道到了，直接输出答案即可。

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
for (int i=1;i<=1;++i) {
    g[X].erase(find(all(g[X]),Y));
    g[Y].erase(find(all(g[Y]),X));
    queue<ll> q;
    vector<char> vis(N + 2);
    vis[X] = true;
    q.push(X);
    vector<ll> parent(N + 2);
    while (!q.empty()) {
        auto u=q.front();
        q.pop();
        if (vis[Y]) {
            break;
        }
        for (auto to:g[u]) {
            if (vis[to]) continue;
            vis[to]=true;
            parent[to]=u;
            q.push(to);
        }
    }
    if (!vis[Y]) {
        break;
    }
    cout<<"Yes\n";
    vector<ll> cycle_ls;
    for (ll node=Y;node!=X;node=parent[node]) {
        edge_ls.erase(lower_bound(all(edge_ls),
            pair{min(node,parent[node]),max(node,parent[node])}));
        cycle_ls.push_back(node);
        cout<<parent[node]<<" "<<node<<"\n";
    }
    {
        edge_ls.erase(lower_bound(all(edge_ls),
            pair{X,Y}));
        cycle_ls.push_back(X);
        cout<<Y<<" "<<X<<"\n";
    }
    sort(all(cycle_ls));
    for (auto [u,v]:edge_ls) {
        if (binary_search(all(cycle_ls),u) ) {
            cout<<v<<" "<<u<<"\n";
        }else if (binary_search(all(cycle_ls),v)){
            cout<<u<<" "<<v<<"\n";
        }else {
            cout<<u<<" "<<v<<"\n";
        }
    }
    return;
}

如果没有包含 X→YX\to Y 的这个环，就从 XX 出发，随便找一个这个无弦环即可。

image

为什么需要这两个部分呢？

image

只要我们在第一阶段排除这样子的包含 X→YX\to Y 的这个环，我们找到的环上的点的边就不会和 YY 相连。（可以避免出现一些奇奇怪怪的情况）

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
if (isout==false){
    g[X].push_back(Y);
    g[Y].push_back(X);
    // 没有边权，可以直接使用bfs得到最小环。
    queue<ll> q;
    vector<char> vis(N + 2);
    vis[X] = true;
    q.push(X);
    vector<ll> parent(N + 2);
    // 我们找的环，不仅可以包含这个 X - Y 这条边，也可以不包含 X-Y 这条边
    // 只要把 X，Y 诱导的我们的环上即可
    ll st_ed_cycle = 0, another_pa_st_ed = 0;
    while (!q.empty()) {
        auto u = q.front();
        q.pop();
        if (st_ed_cycle != 0) {
            break;
        }
        for (auto to: g[u]) {
          // 排除 parent 点
            if (to == parent[u]) continue;
            // 一旦只要不是 parent 点就遍历到了，那就是遇到环了
            if (vis[to]) {
                another_pa_st_ed = u;
                st_ed_cycle = to;
                continue;
            }
            vis[to] = true;
            parent[to] = u;
            q.push(to);
        }
    }
    // 一个环都没有找到？说明图本身是一颗树
    if (st_ed_cycle == 0) {
        cout << "No\n";
        return;
    }
    vector<ll> order_of_cycle,another_part_of_cycle;
    vector<char>  vis_route(N+2);
    // bfs 还原路径，比较难的地方就是环被砍成了了两半
    // 第一段路径，使用这个 parent 还原
    for (ll i=st_ed_cycle;i!=X;i=parent[i]) {
        order_of_cycle.push_back(i);
        vis_route[i]=true;
    }
    vis_route[X]=true;
    order_of_cycle.push_back(X);
    ll overlap_node=0;
    // 第二段路径还原
    for (ll i=another_pa_st_ed;overlap_node=i,!vis_route[i];i=parent[i]) {
        vis_route[i]=true;
        another_part_of_cycle.push_back(i);
    }
    reverse(all(order_of_cycle));
    order_of_cycle.insert(order_of_cycle.end(),all(another_part_of_cycle));
    order_of_cycle.push_back(overlap_node);
    // order_of_cycle.insert(find(all(order_of_cycle),overlap_node)+1 , order_of_cycle.front());
    // 接下来生成这个序列
    vector<pair<ll,ll>> out_ls;
    for (int i=0;i<SZ(order_of_cycle)-1;++i) {
        ll u=order_of_cycle[i],v=order_of_cycle[i+1];
        edge_ls.erase(lower_bound(all(edge_ls),
            pair{min(u, v), max(u, v)}));
        // cout<<u<<" "<<v<<"\n";
        out_ls.emplace_back(u,v);
    }
    if (!vis_route[Y] ) {
        edge_ls.erase(lower_bound(all(edge_ls),
           pair{X, Y }));
        vis_route[Y]=true;
        // cout<<Y<<" "<<X<<"\n";
        out_ls.emplace_back(Y,X);
    }
    // for (ll u=overlap_node,v=order_of_cycle.front();false;) {
    //     edge_ls.erase(lower_bound(all(edge_ls),
    //         pair{min(u, v), max(u, v)}));
    //     // cout<<u<<" "<<v<<"\n";
    //     out_ls.emplace_back(u,v);
    // }
    for (auto [u,v]:edge_ls) {
        if (vis_route[u] ) {
            // cout<<v<<" "<<u<<"\n";
            out_ls.emplace_back(v,u);
        }else if (vis_route[v]){
            // cout<<u<<" "<<v<<"\n";
            out_ls.emplace_back(u,v);
        }else {
            // cout<<u<<" "<<v<<"\n";
            out_ls.emplace_back(u,v);
        }
    }
    cout<<"Yes\n";
    for (auto [u,v]:out_ls) {
        cout<<u<<" "<<v<<"\n";
    }
}

AC代码

AC
https://qoj.ac/submission/2005037

心路历程（WA，TLE，MLE……）

这道题目的 SPJ 怎么写？

编写这道题 SPJ（Special Judge）的核心难点在于：如何验证“无论怎么走都遇不到”这一条件。

因为题目中描述的移动策略是“任意选择一条出边（arbitrarily traverse）”，这意味着玩家的移动是不确定的。你不能只模拟一条路径，而是必须模拟所有可能的路径。

核心思路：集合模拟（Set Simulation）

要在 SPJ 中解决这个问题，关键点不是记录 Alice 和 Bob “在哪一个点”，而是记录他们当前可能在哪些点的集合。

由于 N≤300N \le 300，我们可以使用 C++ 的 std::bitset<305> 来高效地维护这个集合。

SPJ 的具体实现步骤

1. 基础校验 (Basic Validation)

首先，必须确保选手输出的图是合法的：

  • 边数对应：选手输出的有向边必须和输入的无向边一一对应（通过 multiset 或排序后比对）。

  • 点范围：点的编号在 1…N1 \dots N 之间。

2. 状态定义 (The Critical Point)

这是 SPJ 最关键的部分。

  • 设 SA(t)S_A^{(t)} 为第 tt 轮结束时，Alice 可能所在的所有顶点的集合。

  • 设 SB(t)S_B^{(t)} 为第 tt 轮结束时，Bob 可能所在的所有顶点的集合。

初始状态：

SA(0)={Alicestart},SB(0)={Bobstart}S_A^{(0)} = \{Alice_{start}\}, \quad S_B^{(0)} = \{Bob_{start}\}

3. 状态转移 (Transition)

每一轮模拟时，我们需要计算下一轮的集合 S(t+1)S^{(t+1)}。规则如下：

对于集合中的每一个点 u∈S(t)u \in S^{(t)}：

  • 情况 A（有出边）：如果 uu 有出边指向 v1,v2,…v_1, v_2, \dots，那么在下一轮，Alice/Bob 可能会出现在这些邻居中的任何一个。将 {v1,v2,… }\{v_1, v_2, \dots\} 全部加入 S(t+1)S^{(t+1)}。

  • 情况 B（无出边）：如果 uu 没有出边，根据题目规则，玩家停留在原地。将 uu 加入 S(t+1)S^{(t+1)}。

用位运算表示非常快：

1
2
3
4
5
6
7
8
9
10
next_mask = 0;
for (int u = 1; u <= n; u++) {
    if (current_mask.test(u)) { // 如果当前可能在 u
        if (adj[u].none()) {    // u 没有出边
            next_mask.set(u);   // 下一轮还在 u
        } else {                // u 有出边
            next_mask |= adj[u]; // 下一轮可能在 u 的所有邻居
        }
    }
}

4. 碰撞检测 (Collision Check)

在任何时刻 tt，如果 Alice 和 Bob 的可能位置集合有交集，说明存在一种走法让他们相遇，判为 WA。

  • 判定条件：(S_A & S_B).any() == true

5. 终止条件 (Termination)

模拟不能无限进行下去。我们有两个终止条件：

  1. 相遇：检测到交集，直接 quitf(_wa, ...)****。

  2. **死循环（安全）：**如果当前的“状态对” (SA,SB)(S_A, S_B) 曾经出现过，说明我们进入了一个循环，而且在这个循环中没有发生碰撞。那么继续跑下去也不会碰撞。此时判为 AC。

  • 使用 set<pair<string, string>> history 记录 bitset 的状态。

完整的 SPJ 代码结构 (基于 testlib.h)

这是一个标准的写法，你可以直接参考：

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include "testlib.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 305;

int main(int argc, char* argv[]) {
    registerTestlibCmd(argc, argv);

    int t = inf.readInt(); // 读取测试用例数
    while (t--) {
        int n = inf.readInt();
        int m = inf.readInt();
        int startA = inf.readInt();
        int startB = inf.readInt();

        // 1. 读取标准输入的边 (用于校验)
        multiset<pair<int, int>> edges;
        for (int i = 0; i < m; i++) {
            int u = inf.readInt();
            int v = inf.readInt();
            if (u > v) swap(u, v);
            edges.insert({u, v});
        }

        string ja = ans.readToken(); // Jury's answer
        string pa = ouf.readToken(); // Participant's answer

        if (ja != pa) {
            quitf(_wa, "Answer mismatch! Expected %s, found %s", ja.c_str(), pa.c_str());
        }

        if (pa == "No") continue; // 如果是 No，且 Jury 也是 No，这组过了

        // 2. 建图 & 校验选手输出的边
        vector<bitset<MAXN>> adj(n + 1);
        vector<bool> has_outgoing(n + 1, false);

        for (int i = 0; i < m; i++) {
            int u = ouf.readInt();
            int v = ouf.readInt();
            
            // 校验边是否存在于原图中
            int u_chk = u, v_chk = v;
            if (u_chk > v_chk) swap(u_chk, v_chk);
            auto it = edges.find({u_chk, v_chk});
            if (it == edges.end()) {
                quitf(_wa, "Edge %d->%d invalid or used twice", u, v);
            }
            edges.erase(it);

            // 建图
            adj[u].set(v);
            has_outgoing[u] = true;
        }

        // 3. 核心模拟逻辑
        bitset<MAXN> curA, curB;
        curA.set(startA);
        curB.set(startB);

        // 状态记忆化，防止死循环超时
        set<pair<string, string>> visited_states; 
        
        bool ok = true;
        int steps = 0;
        
        // 这里的 20000 是一个保险值，实际上如果有环，visited_states 会更早截断
        while (steps++ < 20000) {
            // Check Collision
            if ((curA & curB).any()) {
                quitf(_wa, "Alice and Bob meet at step %d", steps);
            }

            // Check Cycle (Memoization)
            string sa = curA.to_string();
            string sb = curB.to_string();
            if (visited_states.count({sa, sb})) {
                // 状态重复，且之前没遇到 WA，说明进入安全循环
                break; 
            }
            visited_states.insert({sa, sb});

            // Move Alice
            bitset<MAXN> nextA;
            for (int i = 1; i <= n; i++) {
                if (curA[i]) {
                    if (!has_outgoing[i]) nextA.set(i); // Stay
                    else nextA |= adj[i];               // Move
                }
            }

            // Move Bob
            bitset<MAXN> nextB;
            for (int i = 1; i <= n; i++) {
                if (curB[i]) {
                    if (!has_outgoing[i]) nextB.set(i); // Stay
                    else nextB |= adj[i];               // Move
                }
            }

            curA = nextA;
            curB = nextB;
        }
    }

    quitf(_ok, "All test cases passed!");
}

总结

这道题 SPJ 的精髓在于不要去想“他们走了哪条路”，而是利用 NN 较小的特点，并行追踪“他们可能在的所有位置”。只要这两个位置集合永远不相交，选手的答案就是正确的。