原题链接：https://www.luogu.com.cn/problem/P5663。
更好的使用方式：https://www.luogu.com.cn/article/0o6pvn64。
警告：严禁抄袭。
分析
此题是一道图论的题目，可以将每个工人看成一个点，将双向的零件传送带看作无向边。
只管的做法是按照题目的描述规则，使用递归直接模拟，这样可以通过前 $8$ 个测试点，得到 $40$ 分。对于满分做法，需要观察这个无向图本身的性质，容易发现 $x$ 号点生产一个 $L$ 阶段零件时，如果能找到一条从 $x$ 号点到 $1$ 号点提供原材料。
通过样例 $2$ 的情况，我们发现 $3$ 号点到 $1$ 号点有两条简单的路径，$3\to2\to1$ 与 $3\to4\to5\to1$。那么，如果 $3$ 号点想生产第一阶段的零件，因为两条简单路径的最短长度是 $2$，因此至少要生产第 $2$ 阶段的零件才能到达 $1$ 号点。此外，所有大于 $2$ 的偶数阶段也都是需要 $1$ 号点给材料的，因此会有 $3\to2\to1\cdots\to2\to1$ 这样的方式使得 $1$ 号点提供原材料，因为可以通过 $3\to4\to5\to1\cdots\to5\to1$ 的方式到达一号点。
由此可得，只需预处理出 $1$ 号点到其他所有点的最短奇数路径和最短偶数路径的长度。当 $x$ 号点生产一个 $L$ 阶段的零件时，如果 $L$ 是奇数且 $L$ 大于等于 $x$ 号点到 $1$ 号点的最短奇数路径长度，就需要 $1$ 号点生产原材料。如果 $L$ 是偶数且 $L$ 大于等于 $x$ 号点到 $1$ 号点的最短偶数路径长度，就需要 $1$ 号点生产原材料。
AC 代码
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
| #include<bits/stdc++.h>
using namespace std;
int n, m, Q;
vector<int> g[100005];
int odd[100005], even[100005];
queue<int> q;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> Q;
for(int i = 1;i <= m;i++){
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
memset(odd, 0x3f, sizeof(odd));
memset(even, 0x3f, sizeof(even));
even[1] = 0;
q.push(1);
while(!q.empty()){
int u = q.front();
q.pop();
for(int i = 0;i < g[u].size();i++){
int v = g[u][i];
bool flag = false;
if(odd[u] + 1 < even[v]){
even[v] = odd[u] + 1;
flag = true;
}
if(even[u] + 1 < odd[v]){
odd[v] = even[u] + 1;
flag = true;
}
if(flag)
q.push(v);
}
}
for(int i = 1;i <= Q;i++){
int a, L;
cin >> a >> L;
if(L % 2 == 0 && even[a] <= L)
cout << "Yes" << endl;
else if(L % 2 == 1 && odd[a] <= L)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
|
AC 记录：https://www.luogu.com.cn/record/197005888。