CSP 2019 第四题： 加工零件
题目链接
题目：
知识点：
图、最短路径、bfs
思路：
- 先都读懂题，题目的零件加工是需要相邻点的参与，除非不加工，否则相邻的一定会提供零件
- 题目要求的是某个节点产某个阶段的零件，问第一个节点需不需要提供零件（原材料）。不难看出，这是和路径相关的题目，节点N 要生产第L阶段的零件需要节点1提供零件，那么N到第一个节点的路径至少为L-1，这是直观看出来的，但实际上，要使得该节点到第一个节点的路径最小，我们得求出最短路径，也就是BFS，当L比路径大时，在节点1和N之前肯定会多出2的倍数的路径（在两个节点之间可以多生产几个阶段），因此只要加工的阶段L==最短路径+2n即可，具体在哪些节点多生产几次可以不关心，当最短路径为奇数，+2n后依旧是奇数，反之则是偶数。
- 以第四个节点生产L5阶段为例子，路径为3，L5则是在第一阶段和第二阶段多生产一次即可。因此最短路径是奇数，L就必须要求是大于等于最短路径的奇数，反之，最短路径是偶数，则L必须是大于等于最短路径的偶数
数据约束：
数据无特别约束，bfs时间复杂度为O(n)，无超时
代码参考：
- 由于储存图的的数据关系时为了方便遍历用邻接矩阵，矩阵设为动态数组为了方便储存邻接关系，如果时静态二维数组就还得多遍历几次
- 写完才发现代码有点冗长，处理就奇偶的最短路径时，数组可以用二维数组，a[1][]存偶，奇存a[][1],这样判断时直接用a[][y%2]即可，不用多些几个判断
- 最短路径除了BFS还有 Dijkstra、SPFA等，但是对于无权值的最短路径，BFS也就足够用了
//建图,利用bfs找出最短的技术路径和偶数路径(也可以spfa和jst)
#include<bits/stdc++.h>
#define MAX_N 200005
using namespace std;
int n,m,l;
vector<int> v[MAX_N];
struct stu{int k,dis;//记录点和到该点的距离 stu(int x=0,int l=0) : k(x),dis(l){};//设置初始化 默认为0
};
queue <stu> q;
int even[MAX_N],odd[MAX_N];//分别储存奇偶路径
void bfs();
int main(){cin>>n>>m>>l; //n个工人,m条数 ,l个数据 int x,y;for(int i=1;i<=m;i++){cin>>x>>y;v[x].push_back(y),v[y].push_back(x); //邻接表储存结果 }bfs();for(int i=1;i<=l;i++){cin>>x>>y; if(y%2==0){if(odd[x]<=y&&odd[x]!=-1){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;} }else{even[x]<=y&even[x]!=-1 ? cout<<"Yes"<<endl : cout<<"No"<<endl;}} return 0;
}
void bfs(){memset(odd,-1,sizeof(odd));memset(even,-1,sizeof(even));//每次进来初始化节点情况q.push(stu(1,0)); //第一个数据入队 while(!q.empty()){stu now = q.front();q.pop();int x = now.k;//vector数组长度也可以是 for(int p =0;p<(int) v[x].size();p++){ //遍历该行的邻接表(相邻节点) int y= v[x][p];int num = now.dis+1;//如果没被访问过就直接更新否则退出 if(num%2==0){//偶数 if(odd[y] != -1) continue;else odd[y] = num;}else{if(even[y]!=-1) continue;else even[y] = num;}
// cout<<"bfs:"<<y<<"： "<<num<<endl;q.push(stu(y,num));}}}