[CSP-J 2019] 加工零件

GitHub 跳转原题关系图返回列表

把问题转成从 1 到 a 是否存在长度恰好为 L 的游走，用奇偶分层图 BFS 求最短同奇偶步数。

OJ: luogu

题目 ID: P5663

难度:普及+/提高

标签:图论bfs最短路

日期: 2026-06-19 19:38

题意

给出一个无向图。对每张工单 (a, L)，问 1 号工人会不会在“第 L 层传播”里被卷入，从而需要给别人提供原材料。

思路

最直接的办法是按层数逐层扩展，做一个“恰好走 step 步能到哪些点”的 DP。

先看一个可以直接验证想法的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44#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; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<pair<int, int>> query(q);
    int maxL = 0;
    for (int i = 0; i < q; ++i) {
        cin >> query[i].first >> query[i].second;
        maxL = max(maxL, query[i].second);
    }

    vector<vector<int>> can(maxL + 1, vector<int>(n + 1, 0));
    can[0][1] = 1;

    for (int step = 1; step <= maxL; ++step) {
        for (int u = 1; u <= n; ++u) {
            if (!can[step - 1][u]) {
                continue;
            }
            for (int v : g[u]) {
                can[step][v] = 1;
            }
        }
    }

    for (auto [a, L] : query) {
        cout << (can[L][a] ? "Yes" : "No") << '\n';
    }
    return 0;
}

下面是另一种「状态搜索」风格的暴力写法。它把状态写成“已经走了几步、当前在哪个点”，再递归枚举下一步走向哪个相邻点：

另一种暴力写法：状态搜索

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67// brute_01_style.cpp：状态搜索风格暴力，用递归枚举每一步走向哪个相邻点。
#include <bits/stdc++.h>
using namespace std;

int n, m, q;
int max_l;
vector<vector<int> > g;
vector<pair<int, int> > query_list;
vector<vector<unsigned char> > can_reach; // can_reach[step][u] 表示恰好 step 步能到 u
vector<vector<unsigned char> > expanded;  // expanded[step][u] 表示这个状态已经向后扩展过

void dfs_walk(int step, int u) {
    can_reach[step][u] = 1;
    if (step == max_l) {
        return;
    }
    if (expanded[step][u]) {
        return;
    }
    expanded[step][u] = 1;

    // 下一步可以选择走向任意一个相邻工人。
    for (int i = 0; i < (int)g[u].size(); i++) {
        int v = g[u][i];
        dfs_walk(step + 1, v);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> q;
    g.assign(n + 1, vector<int>());

    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    query_list.resize(q);
    max_l = 0;
    for (int i = 0; i < q; i++) {
        int a, l;
        cin >> a >> l;
        query_list[i] = make_pair(a, l);
        max_l = max(max_l, l);
    }

    can_reach.assign(max_l + 1, vector<unsigned char>(n + 1, 0));
    expanded.assign(max_l + 1, vector<unsigned char>(n + 1, 0));
    dfs_walk(0, 1);

    for (int i = 0; i < q; i++) {
        int a = query_list[i].first;
        int l = query_list[i].second;
        if (can_reach[l][a]) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }

    return 0;
}

brute.cpp 用 can[step][u] 直接表示恰好 step 步能否到点 u，适合小数据对拍，但正式数据里 L 可达 1e9，显然不能这样推。

关键观察是：工单 (a, L) 等价于问“从 1 到 a 是否存在长度恰好为 L 的游走”。在无向图中，只要某种奇偶性的路径存在，就可以通过沿一条边来回走，把长度每次多补 2。

因此只需要知道：

到每个点的最短偶数步长度
到每个点的最短奇数步长度

这张图展示样例 1 的链结构：

graph G {
  1 -- 2;
  2 -- 3;
}

从这张图可以看出：

到 1 的偶数步最短是 0
到 2 的奇数步最短是 1
到 3 的偶数步最短是 2

一旦这些最短同奇偶步数知道了，查询 (a, L) 时，只要 dist[a][L mod 2] <= L，就说明可以先走最短那条同奇偶路径，再通过“来回两步”把长度补到正好 L。

只有 $a = 1$ 且 L 为偶数时要额外小心：dist[1][0] = 0 只是空路径，不能算作真的发生了一次传播。因此这里必须要求存在正长度偶数游走；无向图里只要 1 号点有邻边，最短这种游走就是 2。

实现时，把每个点拆成两个状态 (u,0) 和 (u,1)，表示走到 u 时步数奇偶为 $0/1$ 。从 (1,0) 出发做 BFS，每经过一条边就翻转奇偶。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

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; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    vector<array<int, 2>> dist(n + 1, {INF, INF});
    queue<pair<int, int>> qu;
    dist[1][0] = 0;
    qu.push({1, 0});

    // 分层图 BFS：状态 (u, p) 表示到点 u、步数奇偶为 p 的最短长度。
    while (!qu.empty()) {
        auto [u, p] = qu.front();
        qu.pop();
        for (int v : g[u]) {
            int np = p ^ 1;
            if (dist[v][np] != INF) {
                continue;
            }
            dist[v][np] = dist[u][p] + 1;
            qu.push({v, np});
        }
    }

    int min_even_self = (g[1].empty() ? INF : 2);

    while (q--) {
        int a, L;
        cin >> a >> L;
        int p = L & 1;
        int need = dist[a][p];
        if (a == 1 && p == 0) {
            need = min_even_self;
        }
        if (need <= L) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
    return 0;
}

复杂度

分层图只有 2n 个状态，BFS 是 $O(n + m)$ ，每个查询是 $O(1)$ ，总复杂度是 $O(n + m + q)$ 。

总结

这题的关键不是按层硬模拟，而是把问题转成“同奇偶最短游走”。抓住“无向图里可以随时补两步”这个性质后，答案就只剩一次奇偶分层 BFS。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P5663 [CSP-J 2019] 加工零件

题目描述

凯凯的工厂正在有条不紊地生产一种神奇的零件，神奇的零件的生产过程自然也很神奇。工厂里有 $n$ 位工人，工人们从 $1 \sim n$ 编号。某些工人之间存在双向的零件传送带。保证每两名工人之间最多只存在一条传送带。

如果 $x$ 号工人想生产一个被加工到第 $L\,(L \gt 1)$ 阶段的零件，则所有与 $x$ 号工人有传送带直接相连的工人，都需要生产一个被加工到第 $L - 1$ 阶段的零件（但 $x$ 号工人自己无需生产第 $L - 1$ 阶段的零件）。

如果 $x$ 号工人想生产一个被加工到第 $1$ 阶段的零件，则所有与 $x$ 号工人有传送带直接相连的工人，都需要为 $x$ 号工人提供一个原材料。

轩轩是 $1$ 号工人。现在给出 $q$ 张工单，第 $i$ 张工单表示编号为 $a_i$ 的工人想生产一个第 $L_i$ 阶段的零件。轩轩想知道对于每张工单，他是否需要给别人提供原材料。他知道聪明的你一定可以帮他计算出来！

输入格式

第一行三个正整数 $n$ ， $m$ 和 $q$ ，分别表示工人的数目、传送带的数目和工单的数目。

接下来 $m$ 行，每行两个正整数 $u$ 和 $v$ ，表示编号为 $u$ 和 $v$ 的工人之间存在一条零件传输带。保证 $u \neq v$ 。

接下来 $q$ 行，每行两个正整数 $a$ 和 $L$ ，表示编号为 $a$ 的工人想生产一个第 $L$ 阶段的零件。

输出格式

共 $q$ 行，每行一个字符串 Yes 或者 No。如果按照第 $i$ 张工单生产，需要编号为 1 的轩轩提供原材料，则在第 $i$ 行输出 Yes；否则在第 $i$ 行输出 No。

输入输出样例 #1

输入 #1

text

输出 #1

text

1
2
3
4
5
6No
Yes
No
Yes
No
Yes

输入输出样例 #2

输入 #2

text

输出 #2

text

1
2
3
4
5No
Yes
No
Yes
Yes

说明/提示

样例 1 说明

编号为 1 的工人想生产第 1 阶段的零件，需要编号为 2 的工人提供原材料。

编号为 2 的工人想生产第 1 阶段的零件，需要编号为 1 和 3 的工人提供原材料。

编号为 3 的工人想生产第 1 阶段的零件，需要编号为 2 的工人提供原材料。

编号为 1 的工人想生产第 2 阶段的零件，需要编号为 2 的工人生产第 1 阶段的零件，需要编号为 1 和 3 的工人提供原材料。

编号为 2 的工人想生产第 2 阶段的零件，需要编号为 1 和 3 的工人生产第 1 阶段的零件，他/她们都需要编号为 2 的工人提供原材料。

编号为 3 的工人想生产第 2 阶段的零件，需要编号为 2 的工人生产第 1 阶段的零件，需要编号为 1 和 3 的工人提供原材料。

样例 2 说明

编号为 1 的工人想生产第 1 阶段的零件，需要编号为 2 和 5 的工人提供原材料。

编号为 1 的工人想生产第 2 阶段的零件，需要编号为 2 和 5 的工人生产第 1 阶段的零件，需要编号为 1,3,4 的工人提供原材料。

编号为 1 的工人想生产第 3 阶段的零件，需要编号为 2 和 5 的工人生产第 2 阶段的零件，需要编号为 1,3,4 的工人生产第 1 阶段的零件，需要编号为 2,3,4,5 的工人提供原材料。

编号为 1 的工人想生产第 4 阶段的零件，需要编号为 2 和 5 的工人生产第 3 阶段的零件，需要编号为 1,3,4 的工人生产第 2 阶段的零件，需要编号为 2,3,4,5 的工人生产第 1 阶段的零件，需要全部工人提供原材料。

编号为 1 的工人想生产第 5 阶段的零件，需要编号为 2 和 5 的工人生产第 4 阶段的零件，需要编号为 1,3,4 的工人生产第 3 阶段的零件，需要编号为 2,3,4,5 的工人生产第 2 阶段的零件，需要全部工人生产第 1 阶段的零件，需要全部工人提供原材料。

数据规模与约定

共 $20$ 个测试点。

对所有测试点保证 $1 \leq u, v, a \leq n$ 。

测试点 $1\sim4$ ， $1 \leq n, m \leq 1000$ ， $q = 3$ ， $L = 1$ 。

测试点 $5\sim8$ ， $1 \leq n, m \leq 1000$ ， $q = 3$ ， $1 \leq L \leq 10$ 。

测试点 $9\sim12$ ， $1 \leq n, m, L \leq 1000$ ， $1 \leq q \leq 100$ 。

测试点 $13\sim16$ ， $1 \leq n, m, L \leq 1000$ ， $1 \leq q \leq 10^5$ 。

测试点 $17\sim20$ ， $1 \leq n, m, q \leq 10^5$ ， $1 \leq L \leq 10^9$ 。

[CSP-J 2019] 加工零件

目录

题意

思路

代码

复杂度

总结

一图流解析