[CSP-J 2019] 加工零件

知识点

无向图、奇偶性、分层图、广度优先搜索

解题思路

沿生产需求回溯L层，需要1号工人提供原料，当且仅当从a到1存在长度恰为L的游走。无向图允许重复经过边；若已有同奇偶长度的游走，可沿任意一条经过的边往返，使长度每次增加2。因此从1号点对“顶点、长度奇偶”二层状态做BFS，得到每个点到1的最短奇长度和最短偶长度。查询检查相应奇偶的距离是否不超过L。若1号点完全孤立，任何正L都不可能，单独判No。

正确性说明

BFS在状态图中跨一条原图边同时翻转奇偶，故求出的d[a][L mod 2]是对应奇偶游走的最短长度。若存在长度L的游走，则这个最短长度必不大于L；反之，若最短长度不大于L，两者同奇偶，其差为非负偶数，可通过往返同一条边补足。最短距离为0且需要延长时，1号点至少有一条邻边才能往返，代码显式排除孤立点，故判定充分且必要。

易错点

这里是游走而非简单路径；同一顶点要记录两种奇偶状态；不能只求普通最短路。图可能不连通，未访问状态为-1，不能按负数≤L误判。输出Yes/No大小写与原题一致。

复杂度

时间O(n+m+q)，空间O(n+m)，每次查询O(1)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n,m,q; cin>>n>>m>>q;
    vector<vector<int>> g(n+1);
    for(int i=0,u,v;i<m;++i){cin>>u>>v;g[u].push_back(v);g[v].push_back(u);}
    vector<array<int,2>> d(n+1,array<int,2>{-1,-1});
    queue<pair<int,int>> que;d[1][0]=0;que.push({1,0});
    while(!que.empty()){
        auto [u,p]=que.front();que.pop();
        for(int v:g[u]) if(d[v][p^1]==-1){
            d[v][p^1]=d[u][p]+1;que.push({v,p^1});
        }
    }
    while(q--){
        int a;long long L;cin>>a>>L;
        int dis=d[a][L&1];
        bool ok=!g[1].empty() && dis!=-1 && dis<=L;
        cout<<(ok?"Yes":"No")<<'\n';
    }
    return 0;
}