CSP 真题解析：[CSP-J 2019-T4] 加工零件

[CSP-J 2019-T4]加工零件

摘要：本文详细解析了 CSP-J 2019 第四题「加工零件」的解题思路与 C++ 实现。题目本质上是判断无向图中从 1 号点出发，能否恰好走 L 步到达目标点 a。利用「反复横跳不改变路径奇偶性」的图论性质，问题转化为求 1 号点到各点的奇数最短路和偶数最短路。文章通过 BFS 预处理奇偶最短距离，实现 O(1) 在线查询，并梳理了孤立点特判、数组越界、无穷大初始化等常见易错点，附带完整参考代码。

题目描述

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

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

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

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

输入格式

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

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

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

输出格式

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

输入输出样例 #1

输入 #1

3 2 6 1 2 2 3 1 1 2 1 3 1 1 2 2 2 3 2

输出 #1

No Yes No Yes No Yes

输入输出样例 #2

输入 #2

5 5 5 1 2 2 3 3 4 4 5 1 5 1 1 1 2 1 3 1 4 1 5

输出 #2

No 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 2020个测试点。

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

测试点1 ∼ 4 1\sim41∼4，1 ≤ n , m ≤ 1000 1 \leq n, m \leq 10001≤n,m≤1000，q = 3 q = 3q=3，L = 1 L = 1L=1。

测试点5 ∼ 8 5\sim85∼8，1 ≤ n , m ≤ 1000 1 \leq n, m \leq 10001≤n,m≤1000，q = 3 q = 3q=3，1 ≤ L ≤ 10 1 \leq L \leq 101≤L≤10。

测试点9 ∼ 12 9\sim129∼12，1 ≤ n , m , L ≤ 1000 1 \leq n, m, L \leq 10001≤n,m,L≤1000，1 ≤ q ≤ 100 1 \leq q \leq 1001≤q≤100。

测试点13 ∼ 16 13\sim1613∼16，1 ≤ n , m , L ≤ 1000 1 \leq n, m, L \leq 10001≤n,m,L≤1000，1 ≤ q ≤ 10 5 1 \leq q \leq 10^51≤q≤105。

测试点17 ∼ 20 17\sim2017∼20，1 ≤ n , m , q ≤ 10 5 1 \leq n, m, q \leq 10^51≤n,m,q≤105，1 ≤ L ≤ 10 9 1 \leq L \leq 10^91≤L≤109。

思路要点

工厂里有n nn个工人，工人之间有双向传送带（无向图）。

如果a aa号工人要生产一个第L LL阶段的零件，跟他在图上有边直接相连的所有人就要生产第L − 1 L-1L−1阶段的零件；以此类推，一直传导下去。最后第1 11阶段零件的相邻工人需要提供原材料（也就是倒数第0 00阶段）。

题目问：当a aa号工人生产第L LL阶段零件时，1 11** 号工人（轩轩）是否需要提供原材料？**

关键思路

零件生产的“反向需求传递”，本质上就是在图上走一步。

• a aa需要第L LL阶段→ \rightarrow→找与a aa距离为1 11的人（第L − 1 L-1L−1阶段）→ \rightarrow→找与a aa距离为2 22的人（第L − 2 L-2L−2阶段）→ \rightarrow→...→ \rightarrow→找与a aa距离为L LL的人（提供原材料）。

• 因此，问题等价转化为：在无向图中，从a aa点出发，能否刚好走L LL步到达1 11号点？（因为是双向传送带，从a aa走L LL步到1 11，等价于从1 11号点出发，能否刚好走L LL步到达a aa点。）

• 无向图有一个重要性质：如果从1 11到a aa有一条长度为d dd的路径，那么只要我们在一条边上“反复横跳”（来回走），就可以构造出长度为d + 2 , d + 4 , d + 6 , … d+2, d+4, d+6, \dotsd+2,d+4,d+6,…的路径。****注意：但你无法通过反复横跳把一条偶数长度的路径变成奇数长度！路径长度的奇偶性在反复横跳中是绝对不变的（每次来回必定+ 2 +2+2）。

至此，我们可以总结下思路：要判断能否从1 11走L LL步到达a aa，只需要满足两个条件：

• 奇偶性相同：L LL的奇偶性，必须与从1 11到a aa的某条路径的奇偶性相同。

• 长度足够大：L LL必须≥ \ge≥从1 11到a aa该奇偶性下的最短路径长度（多了的步数我们可以通过反复横跳消耗掉）。

所以，我们只需要针对每个点i ii，求出：

• ev[i]：从1 11号点到i ii号点的偶数最短路径长度。

• od[i]：从1 11号点到i ii号点的奇数最短路径长度。

查询时：

• 如果L LL是奇数：只要L ≥ o d [ a ] L \ge od[a]L≥od[a]，输出Yes，否则No。

• 如果L LL是偶数：只要L ≥ e v [ a ] L \ge ev[a]L≥ev[a]，输出Yes，否则No。

解题步骤

我们以样例 1为例，模拟代码的图构建与 BFS 执行过程：

输入：

n = 3 , m = 2 , q = 6 n=3, m=2, q=6n=3,m=2,q=6

边：( 1 , 2 ) , ( 2 , 3 ) (1,2), (2,3)(1,2),(2,3)

1. 图的初始化与建边 (链式前向星)

代码中使用head,to,nxt数组模拟邻接表：

• 插入边1 ↔ 2 1 \leftrightarrow 21↔2和2 ↔ 3 2 \leftrightarrow 32↔3后，图结构如下：

  1 11的邻居：2 22

  2 22的邻居：3 , 1 3, 13,1

  3 33的邻居：2 22

2. BFS 初始化：设置距离数组起点值

定义ev[maxn](偶数最短路) 和od[maxn](奇数最短路)，初始全部设为无穷大0x3f3f3f3f。

• 起点为1 11号点：走0 00步（偶数）到自己，所以初始化ev[1] = 0。

• 将起点1 11压入队列q1.push(1)。

3. BFS 广度优先搜索更新奇偶最短路径

   我们通过ud(x, y, v)函数进行松弛操作（用当前的步数+ 1 +1+1去更新目标点对应奇偶性的最短路）：

   当前边起点 u	当前边终点 v	松弛逻辑 (当前长度 + 1)	更新后的距离	是否入队
   u = 1	v = 2	ev[1]+1=1 (奇数) 去更新 od[2]	od[2] = 1	push(2)
   u = 2	v = 3	od[2]+1=2 (偶数) 去更新 ev[3]	ev[3] = 2	push(3)
   v = 1	od[2]+1=2 (偶数) 去更新 ev[1]	ev[1]已经是0，不更新	否
   u = 3	v = 2	ev[3]+1=3 (奇数) 去更新 od[2]	od[2]已经是1，不更新	否
   此时队列为空，BFS 结束。

   最终得到的距离表：1 11号点：ev[1] = 0,od[1] = ∞(注意：在图中如果 1 连了 2，其实走 2 步可以回到 1，这里因为连了边，实际循环里如果有边触发会算出ev[1]=0, od[1]=∞；由于 1 到 2 有边，真正跑完样例 1 最终会算出ev[1]=0, od[1]=∞, ev[2]=2, od[2]=1, ev[3]=2, od[3]=3，具体看反复横跳更新)。

4. 处理O ( 1 ) O(1)O(1)判定询问

   • 以工单a = 1, L = 1为例：

     • L = 1 L=1L=1为奇数，我们查看od[1]。

     • 只有当1 11有连边时，1 → 2 → 1 1 \rightarrow 2 \rightarrow 11→2→1长度为 2 (偶数)，而在样例1中无法 1 步走回 1。

     • 此时L < o d [ 1 ] L < od[1]L<od[1]（或o d [ 1 ] od[1]od[1]为无穷大），输出No。

   • 以工单a = 2, L = 1为例：

     • L = 1 L=1L=1为奇数，查看od[2]。

     • 我们查表发现od[2] = 1。

     • 满足l >= od[a]且奇偶性相同，调用jg()函数输出Yes。

本题易错点

• 坑一：孤立点特判

  要点提醒：如果1 11号点没有连出任何一条边，那么任何人想生产零件，1 11号点都绝对无法提供原材料！所以必须加if(!head[1]) { printf("No\n"); continue; }。

• 坑二：数组开二倍空间

  要点提醒：链式前向星存无向图，一条无向边相当于两条有向边。to和nxt数组必须开到maxn * 2，否则会引发数组越界（RE）。

• 坑三：距离数组初始化为无穷大0x3f

  要点提醒：用 BFS 不断更新找最短路径，需要给每个点的初识路径长度设为一个极大值。每个字节被设为0x3f，整型变量实际上变成了0x3f3f3f3f（十进制约 10 亿），这个值足够大（大于题目最大的边长），同时两个0x3f3f3f3f相加不会发生int溢出变成负数。

参考代码

#include<bits/stdc++.h>#definemaxn100005usingnamespacestd;intn,m,q;intk,to[maxn*2],head[maxn],nxt[maxn*2];// 链式前向星存图数组，无向图开两倍空间intev[maxn],od[maxn];// ev: 偶数最短路；od: 奇数最短路queue<int>q1;// BFS 队列voidadde(intu,intv){// 建边: u -> vto[++k]=v;nxt[k]=head[u];head[u]=k;}// 最短路松弛优化函数：用 x + 1 的长度去尝试更新目标值 yvoidud(intx,int&y,intv){if(x+1<y){y=x+1;q1.push(v);// 只有最短路被更新了，才需要入队继续推导}}// 求解从结点 1 出发到每个点的最短奇数路径和偶数路径voidbfs(intx){memset(od,0x3f,sizeof(od));// 初始化为无穷大memset(ev,0x3f,sizeof(ev));ev[x]=0;// 1号点到自己不需要走，偶数长度为 0q1.push(x);while(!q1.empty()){intu=q1.front();q1.pop();for(inti=head[u];i;i=nxt[i]){intv=to[i];ud(ev[u],od[v],v);// u 的偶数路径 + 1 = v 的奇数路径ud(od[u],ev[v],v);// u 的奇数路径 + 1 = v 的偶数路径}}}// 判定函数：l的长度是否大于等于最短路径 c，且它们奇偶性相同voidjg(inta,intl,intc){if(l>=c&&(l%2==c%2)){printf("Yes\n");}else{printf("No\n");}}intmain(){scanf("%d %d %d",&n,&m,&q);while(m--){intu,v;scanf("%d %d",&u,&v);adde(u,v);adde(v,u);// 无向图建双向边}bfs(1);// O(N+M) 预处理 1 号点到所有点的奇偶最短路while(q--){inta,l;scanf("%d %d",&a,&l);// 特判：如果 1 号点是孤立点（没有任何传送带相连），根本无法向外传递if(!head[1]){printf("No\n");continue;}// 根据阶段 L 的奇偶性，选择对应的最短路数组进行比对if(l%2){jg(a,l,od[a]);}else{jg(a,l,ev[a]);}}return0;}