简答题
偏难
#17721
图上移动 题目描述 小 A 有一张包含n 个结点与 m条边的无向图,结点以1,2,...,n 标号。小 A 会从图上选择一个结点作为起点,每一步移动到某个与当前…
图上移动
题目描述
小 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 步之后可能位于的结点数量。
输入样例
输出样例
数据范围
对于20 % 的测试点,保证k=1 。
对于另外20 % 的测试点,保证 1≤n≤50,1≤m≤50 。
对于所有测试点,保证 1≤n≤500,1≤m≤500 ,1≤k≤20 ,1≤ui,vi≤n。
答案与解析
正确答案:<pre class="brush:python;toolbar:false">n, m, k = map(int, input().split())
to = [[] for i in range(n + 2)]
for i in range(m):
x, y = map(int, input().split())
to[x].append(y)
to[y].append(x)
f = [[[False] * (n + 2) for _ in range(n + 2)] for __ in range(k + 2)]
for i in range(1, n + 1):
f[0][i][i] = True
for t in range(1, k + 1):
for x in range(1, n + 1):
for y in range(1, n + 1):
if f[t - 1][x][y]:
for z in to[y]:
f[t][x][z] = True
for i in range(1, n + 1):
Ans = []
for t in range(1, k + 1):
ans = 0
for j in range(1, n + 1):
ans += (f[t][i][j] == True)
Ans.append(str(ans))
print(' '.join(Ans))</pre>
这道题暂未补解析。