匿名用户·2026/5/16markdown1# 图上移动 题解 2 3## 题目分析 4 5我们有一张包含 $n$ 个结点、$m$ 条边的无向图。对于每一个结点 $i$，需要求出从 $i$ 出发，**恰好**走 $1,2,\dots,k$ 步之后，可能位于哪些结点。由于答案只要求结点数量，我们只需统计不同步数下可达结点的个数。 6 7数据范围（修正后）： 8- $1\le n \le 500$ 9- $0\le m \le 500$ 10- $1\le k \le 25$ 11 12按照最暴力的想法，对于每个起点独立进行 BFS/DFS 需要 $O(n(n+m))$ 的代价，再乘上 $k$ 可能较大。但是我们可以利用动态规划一次性求出所有起点在不同步数下的可达性。 13 14## 解题思路 15 16定义三维布尔数组（或用 bitset 优化） 17$f[t][x][y]$ 表示 **从结点 $x$ 出发，恰好走 $t$ 步能否到达结点 $y$**。 18 19**初始化** 20当 $t=0$ 时，只有起点自身是可达的： 21$$ 22f[0][i][i] = 1 \quad (1\le i\le n) 23$$ 24 25**状态转移** 26对于 $t\ge 1$，如果走 $t-1$ 步从 $x$ 能到达 $y$（即 $f[t-1][x][y]=1$），并且存在一条边 $(y,z)$，那么再走一步就能从 $x$ 到达 $z$： 27$$ 28f[t][x][z] = 1 \quad \text{对于所有满足 } f[t-1][x][y]=1 \text{ 且 } (y,z)\in E 29$$ 30 31由于图是无向的，每条边都可以双向移动，不会遗漏。 32 33**统计答案** 34对于起点 $i$ 和步数 $t$，可到达的结点数量为： 35$$ 36\text{ans}(i,t) = \sum_{j=1}^{n} f[t][i][j] 37$$ 38最后按 $i$ 从 $1$ 到 $n$，每行输出 $t=1..k$ 的答案即可。 39 40## 算法说明 41 42整个算法可以分为三步： 43 441. **存图**：使用邻接表存储无向边，每条边存储两次（双向）。 452. **动态规划**：从小到大枚举步数 $t$，枚举起点 $x$，枚举中间结点 $y$，若 $f[t-1][x][y]=1$，则遍历 $y$ 的所有邻居 $z$，将 $f[t][x][z]$ 置为 $1$。 463. **输出**：对于每个起点 $i$ 和步数 $t$，累计 $f[t][i][j]$ 得到答案并输出。 47 48因为 $k,n,m$ 都不大，可以直接用三维数组实现，逻辑清晰。 49 50## 时间复杂度分析 51 52状态数量为 $k \times n \times n$，但在转移时并不是每一对 $(x,y)$ 都会触发邻接表的遍历。最坏情况下，对于每一个 $t$ 和每一个起点 $x$，所有 $y$ 的 $f[t-1][x][y]$ 均为 $1$，此时需要遍历的边数总和为 $O(n \cdot (n+m))$（每个 $y$ 的度数之和约为 $2m$，再加上判断 $f$ 的开销）。 53因此总时间复杂度为 $O(k \cdot n \cdot (n+m))$。 54代入最大值：$25 \times 500 \times (500+500) \approx 1.25\times 10^7$，在 1s 时限内完全可行。 55 56空间复杂度为 $O(k\cdot n^2)$，布尔数组约 $25\times 500\times 500 \approx 6.25\times 10^6$ 字节，即约 6MB，远小于 512MB 限制。若需进一步优化，可以使用滚动数组将 $k$ 维压缩到 2，但本题空间足够，保留三维更易理解。 57 58## 参考代码 59 60下面是完整的 C++ 代码，带有详细注释。 61 62```cpp 63#include <cstdio> 64using namespace std; 65 66const int K = 25; // 最大步数 67const int N = 505; // 最大结点数 68const int E = N << 1; // 无向图边数上限（双向存储） 69 70int n, m, k; 71int h[N], to[E], nx[E], et; // 邻接表 72bool f[K][N][N]; // f[t][x][y] : 从 x 走 t 步能否到 y 73 74// 添加无向边 75void ae(int u, int v) { 76 et++; 77 to[et] = v; 78 nx[et] = h[u]; 79 h[u] = et; 80} 81 82int main() { 83 scanf("%d%d%d", &n, &m, &k); 84 85 // 读入边并建立邻接表 86 for (int i = 1; i <= m; i++) { 87 int u, v; 88 scanf("%d%d", &u, &v); 89 ae(u, v); 90 ae(v, u); 91 } 92 93 // 初始化：走 0 步时，每个结点只能到达自己 94 for (int i = 1; i <= n; i++) 95 f[0][i][i] = true; 96 97 // 动态规划 98 for (int t = 1; t <= k; t++) // 枚举步数 99 for (int x = 1; x <= n; x++) // 枚举起点 100 for (int y = 1; y <= n; y++) // 枚举中间结点 101 if (f[t - 1][x][y]) // 若 t-1 步可到达 y 102 for (int i = h[y]; i; i = nx[i]) // 从 y 走一步到 to[i] 103 f[t][x][to[i]] = true; 104 105 // 输出答案 106 for (int i = 1; i <= n; i++) { // 对于每个起点 i 107 for (int t = 1; t <= k; t++) { // 枚举步数 108 int ans = 0; 109 for (int j = 1; j <= n; j++) // 统计可达结点数 110 if (f[t][i][j]) 111 ans++; 112 // 控制空格输出：最后一个数字后换行 113 printf("%d%c", ans, " \n"[t == k]); 114 } 115 } 116 117 return 0; 118}
h 记录每个结点的第一条边，to 存储邻居，nx 存放下一条边的编号，et 是当前边的总数。函数 ae(u,v) 添加一条 u→v 的有向边，无向图需要调用两次。f[t][x][y] 是布尔值（用 bool 存储）。初始时 f[0][i][i] 为真，其余为假。t, x, y，当 f[t-1][x][y] 为真时，遍历 y 的所有邻居 to[i]，将 f[t][x][to[i]] 置为真。" \n"[t==k] 实现：当 t<k 时输出空格，t=k 时输出换行符。N=505, K=25 为准，即 n≤500，k≤25。bitset 代替 bool 数组，在转移时直接进行位运算，但本题数据量下无需刻意优化。本题是一道典型的图上步数可达性 DP 问题。通过把“起点”也作为状态的一维，我们可以一次性计算出所有起点的答案。时间复杂度 O(kn(n+m)) 可以轻松通过数据范围不大的测试点。掌握这种“步数分层”的思考方式，对解决其它图上有限步移动问题非常有帮助。