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(L1)阶段的零件则所有与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 nnm 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输入 #13 2 6 1 2 2 3 1 1 2 1 3 1 1 2 2 2 3 2输出 #1No Yes No Yes No Yes输入输出样例 #2输入 #25 5 5 1 2 2 3 3 4 4 5 1 5 1 1 1 2 1 3 1 4 1 5输出 #2No 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∼41 ≤ n , m ≤ 1000 1 \leq n, m \leq 10001≤n,m≤1000q 3 q 3q3L 1 L 1L1。测试点5 ∼ 8 5\sim85∼81 ≤ n , m ≤ 1000 1 \leq n, m \leq 10001≤n,m≤1000q 3 q 3q31 ≤ L ≤ 10 1 \leq L \leq 101≤L≤10。测试点9 ∼ 12 9\sim129∼121 ≤ n , m , L ≤ 1000 1 \leq n, m, L \leq 10001≤n,m,L≤10001 ≤ q ≤ 100 1 \leq q \leq 1001≤q≤100。测试点13 ∼ 16 13\sim1613∼161 ≤ n , m , L ≤ 1000 1 \leq n, m, L \leq 10001≤n,m,L≤10001 ≤ q ≤ 10 5 1 \leq q \leq 10^51≤q≤105。测试点17 ∼ 20 17\sim2017∼201 ≤ n , m , q ≤ 10 5 1 \leq n, m, q \leq 10^51≤n,m,q≤1051 ≤ 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 , … d2, d4, d6, \dotsd2,d4,d6,…的路径。****注意但你无法通过反复横跳把一条偶数长度的路径变成奇数长度路径长度的奇偶性在反复横跳中是绝对不变的每次来回必定 2 22。至此我们可以总结下思路要判断能否从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 n3, m2, q6n3,m2,q6边( 1 , 2 ) , ( 2 , 3 ) (1,2), (2,3)(1,2),(2,3)图的初始化与建边 (链式前向星)代码中使用head,to,nxt数组模拟邻接表插入边1 ↔ 2 1 \leftrightarrow 21↔2和2 ↔ 3 2 \leftrightarrow 32↔3后图结构如下1 11的邻居2 222 22的邻居3 , 1 3, 13,13 33的邻居2 22BFS 初始化设置距离数组起点值定义ev[maxn](偶数最短路) 和od[maxn](奇数最短路)初始全部设为无穷大0x3f3f3f3f。起点为1 11号点走0 00步偶数到自己所以初始化ev[1] 0。将起点1 11压入队列q1.push(1)。BFS 广度优先搜索更新奇偶最短路径我们通过ud(x, y, v)函数进行松弛操作用当前的步数 1 11去更新目标点对应奇偶性的最短路当前边起点 u当前边终点 v松弛逻辑 (当前长度 1)更新后的距离是否入队u 1v 2ev[1]11 (奇数) 去更新 od[2]od[2] 1push(2)u 2v 3od[2]12 (偶数) 去更新 ev[3]ev[3] 2push(3)v 1od[2]12 (偶数) 去更新 ev[1]ev[1]已经是0不更新否u 3v 2ev[3]13 (奇数) 去更新 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具体看反复横跳更新)。处理O ( 1 ) O(1)O(1)判定询问以工单a 1, L 1为例L 1 L1L1为奇数我们查看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]Lod[1]或o d [ 1 ] od[1]od[1]为无穷大输出No。以工单a 2, L 1为例L 1 L1L1为奇数查看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溢出变成负数。参考代码#includebits/stdc.h#definemaxn100005usingnamespacestd;intn,m,q;intk,to[maxn*2],head[maxn],nxt[maxn*2];// 链式前向星存图数组无向图开两倍空间intev[maxn],od[maxn];// ev: 偶数最短路od: 奇数最短路queueintq1;// BFS 队列voidadde(intu,intv){// 建边: u - vto[k]v;nxt[k]head[u];head[u]k;}// 最短路松弛优化函数用 x 1 的长度去尝试更新目标值 yvoidud(intx,inty,intv){if(x1y){yx1;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()){intuq1.front();q1.pop();for(intihead[u];i;inxt[i]){intvto[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(lc(l%2c%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(NM) 预处理 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;}