简答题 偏难
#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】

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 。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;cstdio&gt; using namespace std; const int K = 25; const int N = 505; const int E = N &lt;&lt; 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", &amp;n, &amp;m, &amp;k);     for (int i = 1; i &lt;= m; i++) {         int u, v;         scanf("%d%d", &amp;u, &amp;v);         ae(u, v);         ae(v, u);     }     for (int i = 1; i &lt;= n; i++)         f[0][i][i] = 1;     for (int t = 1; t &lt;= k; t++)         for (int x = 1; x &lt;= n; x++)             for (int y = 1; y &lt;= 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 &lt;= n; i++) {         for (int t = 1; t &lt;= k; t++) {             int ans = 0;             for (int j = 1; j &lt;= n; j++)                 ans += f[t][i][j];             printf("%d%c", ans, " \n"[t == k]);         }     }     return 0; }</pre>
这道题暂未补解析。