题解：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

CPP

#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

的状态搞错了，搞成了记录每个节点的路径数，特此告诫后人：

CPP

#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";
	}
}

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

文章操作

做法

AC Code

温馨提示

相关推荐

评论

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