专栏文章

题解：P5663 [CSP-J2019] 加工零件

kkuaiCreator
P5663题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqkotsv
此快照首次捕获于
2025/12/04 06:22
3 个月前
此快照最后确认于
2025/12/04 06:22
3 个月前
查看原文
20252025 年 1010 月 11 日 增加了对孤立顶点的判断。

题目大意

给定一个无向图，图中每个顶点都可以生产邻接点上一个阶段的零件。给点 qq 次询问，第 ii 次询问顶点 aia_i 生产 LL 阶段的零件时顶点 11 是否能够提供原材料。

解题思路

可以将问题转化为从顶点 11 出发走 LL 步是否能够停在顶点 aia_i ，可以重复走走过的顶点。
对下面左侧图进行分析，我们从顶点 11 出发到达顶点 22，可以发现如果步长为 1,3,4,5,6,71,3,4,5,6,7 等都可以到达，但是步长为 22 时无法到达。
如果走红色的路径从 11 到 22，该路径长度为 11，那么 3,5,63,5,6 等更大的奇数步长都能到达。因为大于 11 的奇数数步长我们可以通过重复路径 2−1−22-1-2 最终能够停留在目标顶点。如果走蓝色的路径从 11 到 22，该路径长度为 44，那么 6,8,106,8,10 等更大的偶数步长同样也能停留在目标顶点。
可将问题转换为求奇数步和偶数步的分层图最短路径问题。

解法一：分层建图

如上中间原图，我们可以采用分层建图方式，将原图拆分为 22 层建图。第一层为偶数层，第二层为奇数层，连边时选择偶层连奇层，奇层连偶层。
由于是无权图可以跑 BFS 获取顶点 11 到偶终点编号 nn 或奇终点编号 2n2n 的最短路。根据 LL 的奇偶性选择判断 LL 是否大于等于该条最短路的长度，如果是则输出 Yes 否则输出 No。
CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int > G[N << 1];
int n, m, q, x, y, L, dis[N << 1];
void bfs(int st);
int main() {
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		cin >> x >> y;
		G[x].push_back(y + n);	//分层建图
		G[y + n].push_back(x);
		G[y].push_back(x + n);
		G[x + n].push_back(y);
	}
	bfs(1);
	while (q--) {
		cin >> x >> L;
    if (G[x].size() == 0) cout << "No\n";
		else {
			int res = dis[x + (L & 1) * n];
			if (res <= L) cout << "Yes\n";
			else cout << "No\n";
		}
	}
	return 0;
}
void bfs(int st) {
	memset(dis, 0x3f, sizeof dis);
	queue<int> q;
	q.push(st);
	dis[st] = 0;
	while (q.size()) {
		int hx = q.front();
		q.pop();
		for (auto to : G[hx]) {
			if (dis[to] > dis[hx] + 1) {
				dis[to] = dis[hx] + 1;
				q.push(to);
			}
		}
	}
}

解法二：拆分点权

本质上与解法一相同，不过不用去建分层图而是将点权拆分为两份。在计算走到当前顶点的最短路时，偶距离由邻接点的奇距离更新，同样奇距离由偶距离更新。
CPP
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
vector<int> G[N];
int n, m, q, x, y, L, dis[N][2], vis[N];
void bfs(int st) {
	queue<int> q;
	q.push(st);
	memset(dis, 0x3f, sizeof dis);
	dis[st][0] = 0;
	vis[st] = 1;	
	//vis标记是否在队列中，优化避免一个顶点重复入队
	while (q.size()) {
		int hx = q.front();
		q.pop();
		vis[hx] = 0;
		for (auto to : G[hx]) {
			//奇偶最短路交替更新
			if (dis[to][0] > dis[hx][1] + 1) {
				dis[to][0] = dis[hx][1] + 1;
				if (!vis[to]) q.push(to), vis[to] = 1;
			}
			if (dis[to][1] > dis[hx][0] + 1) {
				dis[to][1] = dis[hx][0] + 1;
				if (!vis[to]) q.push(to), vis[to] = 1;
			}
		}
	}
}
int main() {
	cin >> n >> m >> q;
	for (int i = 1; i <= m; i++) {
		cin >> x >> y;
		G[x].push_back(y);	//无向图双向存图
		G[y].push_back(x);
	}
	bfs(1);
	while (q--) {
		cin >> x >> L;
    if (G[x].size() == 0) cout << "No\n";
		else {
  		int res = dis[x][L & 1];
  		if (res <= L) cout << "Yes\n";
  		else cout << "No\n";
    }
	}
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...