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

· · 题解

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

看到很少有直接写广度优先搜索的，于是就写一篇。

1. 解题思路

其实就是朴素的广度优先搜索，再加上一点分析即可。

这里分享我的经验，分析这种题的规律，先从一个比较简单的图开始模拟。我们从 3 开始，标记为 0。每个节点旁边都有一些黄色的数，代表这些节点在第几轮被访问过。那么，第 5 轮结束后大概就是这个样子：

现在我们把这些看上去杂乱无章的数按照奇偶分类一下，就像这样：

我们来分析一下这些规律：只要有一个偶数轮，则以后的所有偶数轮这个节点都有；只要有一个奇数轮，则以后的所有奇数轮这个节点都有。所以为了看是否需要提供材料，只需要求出每个节点最小的奇数轮和偶数轮即可。

2. 代码实现

代码奇短～

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1e5 + 10;
const int inf = 1e8;
int n, m, q, dis[maxn][2];
vector<int> e[maxn];
queue<pair<int, int>> que;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        e[u].push_back(v); e[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) dis[i][0] = dis[i][1] = inf;
    dis[1][0] = 0; que.push({1, 0});
    while (que.size()) {
        int u = que.front().first, p = que.front().second, d = dis[u][p];
        que.pop();
        for (int v : e[u]) if (dis[v][p ^ 1] > d + 1) {
            dis[v][p ^ 1] = d + 1;
            que.push({v, p ^ 1});
        }
    }
    while (q--) {
        int a, L; cin >> a >> L;
        if (dis[a][L & 1] < inf && dis[a][L & 1] <= L) cout << "Yes\n";
        else cout << "No\n";
    }
    return 0;
}

测评记录