A28337. 图上移动
填空题
困难
知识点
题目描述
图上移动
题目描述
小 A 有一张包含n个结点与m条边的无向图，结点以1，2，...，n 标号。小 A 会从图上选择一个结点作为起点，每一步移动到某个与当前小 A 所在结点相邻的结点。对于每个结点 i（ 1≤i≤n），小 A 想知道从结点i出发恰好移动1，2，...，k步之后，小 A 可能位于哪些结点。由于满足条件的结点可能有很多，你只需要求出这些结点的数量。
输入格式
第一行，三个正整数n，m，k ，分别表示无向图的结点数与边数，最多移动的步数。
接下来m行，每行两个正整数ui，vi ，表示图中的一条连接结点 ui与 vi 的无向边。
输出格式
共n行，第 i行（1≤i≤n ）包含k个整数，第j个整数（ 1≤j≤k）表示从结点i 出发恰好移动j 步之后可能位
于的结点数量。
样例
输入样例 1
4 4 3
1 2
1 3
2 3
3 4输出样例 1
2 4 4
2 4 4
3 3 4
1 3 3数据范围
对于 20% 的测试点，保证k=1 。
对于另外20 % 的测试点，保证 1≤n≤50，1≤m≤50 。
对于所有测试点，保证1≤n≤500 ，1≤m≤500 ，1≤k≤20 ，1≤ui，vi ≤n 。
参考答案
#include <cstdio>
using namespace std;
const int K = 25;
const int N = 505;
const int E = N << 1;
int n, m, k;
int h[N], to[E], nx[E], et;
int f[K][N][N];
void ae(int u, int v) {
et++;
to[et] = v;
nx[et] = h[u];
h[u] = et;
}
int main() {
scanf("%d%d%d", &n, &m, &k);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
ae(u, v);
ae(v, u);
}
for (int i = 1; i <= n; i++)
f[0][i][i] = 1;
for (int t = 1; t <= k; t++)
for (int x = 1; x <= n; x++)
for (int y = 1; y <= n; y++)
if (f[t - 1][x][y])
for (int i = h[y]; i; i = nx[i])
f[t][x][to[i]] = 1;
for (int i = 1; i <= n; i++) {
for (int t = 1; t <= k; t++) {
int ans = 0;
for (int j = 1; j <= n; j++)
ans += f[t][i][j];
printf("%d%c", ans, " \n"[t == k]);
}
}
return 0;
}
上一题
下一题