题解：P11964 [GESP202503 七级] 图上移动

· · 题解

一道非常基础的二维 DP 板子题；

给出一种 DP 的做法，时间复杂度为 O(nk(n+m))。

做法

定义 f_{i,j} 表示第 i 个节点走了 j 步后可以到达的节点数；

考虑状态转移，注意到 f_{i,0} 不论任何情况都等于 1 即任意情况下走 0 步可以到达的节点数只有它自己本身；枚举每个节点可以到达的节点进行叠加就可以推出转移方程了：

f_{u_i,j}=\sum_{i=0}^{n}f_{v_i,j-1}

最后只需要输出整个 f 数组即可。

AC Code

#include <bits/stdc++.h>
using namespace std;
int mp[510][510],cnt[510]/*记录每个节点的邻居数量*/,f[510][21]/*同题解*/,n,m,k;   // 结果数组
int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v;
        mp[u][cnt[u]++]=v,mp[v][cnt[v]++]=u;
    }
    for(int i=1;i<=n;i++) //枚举每个起点
    {
        bool p[510]; //滚动数组优化 
        memset(p,0,sizeof p);
        p[i]=1;
        for(int j=1;j<=k;j++)
        {
            bool c[510];
            memset(c,0,sizeof c);
            for(int u=1;u<=n;u++) //枚举上一个节点 
            {
                if(!p[u]) continue;
                for(int l=0;l<cnt[u];l++) //遍历当前节点的所有邻居
                    c[mp[u][l]]=1;
            }
            int cc=0;
            for(int v=1;v<=n;v++) //看能去哪几个节点，记录 
                cc+=c[v],p[v]=c[v];
            f[i][j]=cc;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=k;j++) cout<<f[i][j]<<' ';
        cout<<"\n";
    }
}

温馨提示

考场上一开始看到的时候就给 f 的状态搞错了，搞成了记录每个节点的路径数，特此告诫后人：

#include<bits/stdc++.h>
using namespace std;
bool mp[510][510];
int f[510][510];
/*
  f[i][j] 表示i节点下移动j步可以获得的节点数量 
*/
int n,m,k,ans;
int main()
{
    cin>>n>>m>>k;
    for(int i=0;i<m;i++)
    {
        int u,v;
        cin>>u>>v;
        mp[u][v]=1,mp[v][u]=1;
    }
    for(int i=1;i<=n;i++) f[i][0]++;
    for(int i=1;i<=n;i++) //当前节点 
    {
        for(int j=1;j<=k;j++)
        {
            for(int r=1;r<=n;r++) //枚举可以去的点 
            {
                if(mp[i][r]) f[i][j]+=f[r][j-1];
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=k;j++) cout<<f[i][j]<<' ';
        cout<<"\n";
    }
}