洛谷P5663题解

原题链接：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 代码

#include<bits/stdc++.h>
using namespace std;
int n, m, Q;
//g[i] 存储所有与i相连的点
vector<int> g[100005];
//odd[i]:从1到i的最短奇数路径的长度
//even[i]:从1到i的最短偶数数路径的长度
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];
			//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。