G7011 [GESP202503 七级] 图上移动 题解

知识点：广度优先搜索、奇偶性、状态扩展。

解题思路

对每个起点在“节点、步数奇偶”扩展图上BFS，求两种奇偶的最短距离。长度j可到的点须满足对应奇偶最短距离≤j，且起点存在可往返的边。

为什么正确

无向图任意一条边可来回补2步，因此同奇偶的更长步数均可实现；扩展BFS给出必要且充分的最短下界。

易错点

要求恰好j步而非至多j步，必须匹配奇偶；孤立点不能通过无意义补步被算入正步数答案。

复杂度

时间O(n(n+m)+n²k)，空间O(n+m)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,k;
    cin>>n>>m>>k;
    vector<vector<int>>g(n);
    while(m--) {
        int u,v;
        cin>>u>>v;
        --u;
        --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int s=0;s<n;s++) {
        vector<array<int,2>>d(n);
        for(auto &x:d)x.fill(-1);
        vector<pair<int,int>>q= {
            {
                s,0
            }
        }
        ;
        d[s][0]=0;
        for(int z=0;z<(int)q.size();z++) {
            auto [u,p]=q[z];
            if(d[u][p]==k)continue;
            for(int v:g[u])if(d[v][p^1]<0) {
                d[v][p^1]=d[u][p]+1;
                q.push_back({v,p^1});
            }
        }
        for(int j=1;j<=k;j++) {
            int ct=0;
            if(!g[s].empty())for(int v=0;v<n;v++)ct+=d[v][j%2]>=0&&d[v][j%2]<=j;
            cout<<ct<<" ";
        }
        cout<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用16个自行生成的测试点。