简答题
偏难
#20429
图上移动 时间限制:1 s,内存限制:512 MB 【问题描述】 小 A 有一张包含 个n 结点与 m 条边的无向图,结点以 1、2、……、n 标号。 小 A…
图上移动
时间限制:1 s,内存限制:512 MB
【问题描述】
小 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】
【样例输出1】
【数据范围】
对于 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:cpp;toolbar:false">#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;
}</pre>
这道题暂未补解析。