题解：P11964 [GESP202503 七级] 图上移动

NewbieZZZ · 2025-03-24 19:29:32 · 题解

写在前面

提供一个较为好想到的、从 BFS 拓展来的解法。可能算暴力乱艹，数据水而已。

欢迎 Hack 本解法复杂度或正确性！

（srds，时间复杂度本人基本不会求。）

解法阐述

样例引入

（放一个样例图方便理解）

首先，手玩样例。这里以 1 为起点：

• 第一步：移动到与起点的两条出边相邻的点 2,3，有 2 个可能的点；
• 第二步：从点 2 移动到与两条出边相邻的点 1,3，从点 3 移动到与三条出边相邻的点 1,2,4，有 4 个可能的点；
• ……

只看每一步，每一个起点时，每次向下走都只尝试访问下一层的节点。\ 有没有觉得像 BFS？

得出解法

回顾一下 BFS 的流程：

• 从队列里弹出一个节点；
• 遍历其出边；
  • 将出边连接到的节点压入队列（这个点要没有被访问过）；
• 如此循环，直到遍历完毕。

在这题中，我们要把起点或每个移动到的节点出边连接的点的数量统计下来。

容易想到每次限制只能向下一层，并存下这些点（但不压入队列，这样才有限制；并且，每个点可以被重复访问）就可以了。需要去重。

对于每一步的移动，输出存下的点的数量即可。

最后，别忘了把移动到的节点在一次向下遍历完后压入队列，这样才可保证队列里有点。走了 k 步后，停止计算。

对于每个节点，循环以上过程。

代码（结合理解）

你们最喜欢的。

#include <bits/stdc++.h>
using namespace std;
// 默认我写了快读（

int n, m, k;
vector<int> e[505];

int main(){
    n = read(), m = read(), k = read();
    for(int i=1, x, y; i<=m; ++i){
        x = read(), y = read();
        e[x].push_back(y);
        e[y].push_back(x);
    }
    for(int i=1; i<=n; ++i, putchar('\n')){
        queue<int> q;
        q.push(i);
        for(int j=1; j<=k; ++j){
            unordered_set<int> s; // 去重；vis 数组去重也行
            while(q.size()){ // 每次向下一步
                int cur = q.front();
                q.pop();
                for(int i : e[cur]){
                    s.insert(i); // 存下这些节点（要去重），以备继续向下
                }
            }
            cout << s.size() << ' ';
            for(int _ : s){
                q.push(_); // 不在乎 BFS 的顺序，直接将下一步的节点压入队列
            }
        }
    }
    return 0;
}

喜提非完隐最劣解（2025.3.24），说不定哪天就被 hack 了。