P5663 [CSP-J2019] 加工零件 题解

· · 题解

原题链接：https://www.luogu.com.cn/problem/P5663。

更好的使用方式：https://www.luogu.com.cn/article/0o6pvn64。

警告：严禁抄袭。

分析

此题是一道图论的题目，可以将每个工人看成一个点，将双向的零件传送带看作无向边。

只管的做法是按照题目的描述规则，使用递归直接模拟，这样可以通过前 8 个测试点，得到 40 分。对于满分做法，需要观察这个无向图本身的性质，容易发现 x 号点生产一个 L 阶段零件时，如果能找到一条从 x 号点到 1 号点提供原材料。

通过样例 2 的情况，我们发现 3 号点到 1 号点有两条简单的路径，3\to2\to1 与 3\to4\to5\to1。那么，如果 3 号点想生产第一阶段的零件，因为两条简单路径的最短长度是 2，因此至少要生产第 2 阶段的零件才能到达 1 号点。此外，所有大于 2 的偶数阶段也都是需要 1 号点给材料的，因此会有 3\to2\to1\cdots\to2\to1 这样的方式使得 1 号点提供原材料，因为可以通过 3\to4\to5\to1\cdots\to5\to1 的方式到达一号点。

由此可得，只需预处理出 1 号点到其他所有点的最短奇数路径和最短偶数路径的长度。当 x 号点生产一个 L 阶段的零件时，如果 L 是奇数且 L 大于等于 x 号点到 1 号点的最短奇数路径长度，就需要 1 号点生产原材料。如果 L 是偶数且 L 大于等于 x 号点到 1 号点的最短偶数路径长度，就需要 1 号点生产原材料。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int n, m, Q;
//g[i] 存储所有与i相连的点
vector<int> g[100005];
//odd[i]:从1到i的最短奇数路径的长度
//even[i]:从1到i的最短偶数数路径的长度
int odd[100005], even[100005];
queue<int> q;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> Q;
    for(int i = 1;i <= m;i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    memset(odd, 0x3f, sizeof(odd));
    memset(even, 0x3f, sizeof(even));
    even[1] = 0;
    q.push(1);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i = 0;i < g[u].size();i++){
            int v = g[u][i];
            //u->i
            bool flag = false;// 是否有优化
            if(odd[u] + 1 < even[v]){
                even[v] = odd[u] + 1;
                flag = true;
            } 
            if(even[u] + 1 < odd[v]){
                odd[v] = even[u] + 1;
                flag = true;
            }
            if(flag) 
                q.push(v);
        }
    }
    for(int i = 1;i <= Q;i++){
        int a, L;
        cin >> a >> L;
        if(L % 2 == 0 && even[a] <= L)
            cout << "Yes" << endl;
        else if(L % 2 == 1 && odd[a] <= L)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}

AC 记录：https://www.luogu.com.cn/record/197005888。