加工零件的题解

原题描述：

题目描述

输入格式

输出格式

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

题目大意：

主要思路：

但是我们怎么才能判断出x走到1时L是偶数还是奇数呢？

初始化：

代码code：

原题描述：

时间限制: 1000ms

空间限制: 524288kB

题目描述

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

如果 $x$ 号工人想生产一个被加工到第 $L$ $(L>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 \ne v$ 。

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

输出格式

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

样例 #1

样例输入 #1

样例输出 #1

No
Yes
No
Yes
No
Yes

样例 #2

样例输入 #2

样例输出 #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 个测试点。

$1 \le u,v,a \le n$ 。

测试点 1~4， $1 \le n,m \le 1000,q = 3, L = 1$ 。

测试点 5~8， $1 \le n,m \le 1000,q = 3,1 \le L \le 10$ 。

测试点 9~12， $1\le n,m,L \le 1000,1 \le q \le 100$ 。

测试点 13~16， $1 \le n,m,L \le 1000, 1\le q \le 10^5$ 。

测试点 17~20， $1 \le n,m,q \le 10^5, 1\le L \le 10^9$ 。

题目大意：

有一张无向图，每次有个节点a要级别为L的部件，则与a直接相连的节点要提供L-1的部件。

当节点a要1级的部件时，那么与a直接相连的节点要提供1个原材料。

问你每次节点1是否提供原材料。

主要思路：

这个题目可以用分类讨论。

分三个部分：（用cnt表示从节点a到1的路径长度（每条边长为1）

L = cnt
L<cnt
L>cnt

对于部分1：

画图来看一下。

当L=cnt时，节点1要提供原材料。

注意：有些童鞋会说：4生产3，那么5又要生产2，不是还要进一步的推导吗？

可是题目中只说是否要1提供原材料，其他的就不用管太多。

第二部分：

L<cnt

还是画图：

我们发现，还没轮到1时，就结束了，说明1不用提供什么。

第三部分：

L>cnt

从x走到1时L是奇数。

1不用提供任何原材料

但是but,当L>cnt 且从x走到1时L是偶数。

这时，1要提供原材料了。

得出结论：

当L = cnt,1要提供原材料。

当L < cnt,1不用提供任何原材料。

当L > cnt,且从x走到1时L-cnt是奇数，1不用提供任何原材料。

当L > cnt,且从x走到1时L是偶数，1要提供原材料。

但是我们怎么才能判断出x走到1时L是偶数还是奇数呢？

int even[100010];// even[x]表示：从1走到x，长度最短为偶数的路径的长度（even是偶数的意思）
int odd[100010];// odd[x]表示：从1走到x，长度最短为奇数的路径的长度（odd是奇数的意思）

注：是最短路径。

奇数-奇数=偶数。

奇数-偶数=奇数

偶数-奇数=奇数

偶数-偶数=偶数。

cnt被替代了

这样我们就发现了：

L是奇数，且l>=odd[x](odd[x]肯定是奇数长度路径）那么就输出"Yes"(等于也输出Yes）

L是奇数，且l<odd[x](odd[x]肯定是奇数长度路径）那么就输出"No"

L是偶数，且l>=even[x](even[x]肯定是偶数长度路径）那么就输出"Yes"(等于也输出Yes）

L是偶数，且l<even[x](even[x]肯定是偶数长度路径）那么就输出"No"

不明白为啥就看重新看一下三个部分。

初始化：

都初始化成0x3f(是一个较大数就可以了）

代码code：

#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int even[100010];// even[x]表示：从1走到x，长度最短为偶数的路径的长度（even是偶数的意思）
int odd[100010];// odd[x]表示：从1走到x，长度最短为奇数的路径的长度（odd是奇数的意思）
vector<vector<int>> v(100010);
//int vis[100010][10010];
void init()
{queue<pair<int,int>> q;q.push({1,0});while(!q.empty()){int node=q.front().first,step=q.front().second;q.pop();for(auto it:v[node]){if(step%2 == 1&&even[it] == 0x3f3f3f3f){even[it] = step+1;
//				vis[it][step+1] = 1;q.push({it,step+1});}if(step%2 == 0&&odd[it] == 0x3f3f3f3f)//有没有走过{odd[it] = step+1;
//				vis[it][step+1] = 1;q.push({it,step+1});}/*有些童鞋会说，这里odd是奇数，可是为啥是放在step%2 == 0，里面不应该是放even吗。回答：step还要+1，因为已经走了这一步，要加一，偶数加1就是奇数，所以是odd放在里面。18行~23行同理*/}}
}
int main()
{cin>>n>>m>>q;for(int i=1;i<=m;i++){int u,v1;cin>>u>>v1;v[u].push_back(v1);v[v1].push_back(u);}memset(odd,0x3f,sizeof(odd));memset(even,0x3f,sizeof(even));init();while(q--){int l,x;cin>>x>>l;if(l%2 == 1){if(l>=odd[x]){cout<<"Yes\n";}else{cout<<"No\n";}}else{if(l>=even[x]){cout<<"Yes\n";}else{cout<<"No\n";}}}return 0;
}