题解：P5663 [CSP-J2019] 加工零件
kuaiCreator
·
·
题解
## 题目大意
给定一个无向图，图中每个顶点都可以生产邻接点上一个阶段的零件。给点 $q$ 次询问，第 $i$ 次询问顶点 $a_i$ 生产 $L$ 阶段的零件时顶点 $1$ 是否能够提供原材料。
## 解题思路
可以将问题转化为从顶点 $1$ 出发走 $L$ 步是否能够停在顶点 $a_i$ ，可以重复走走过的顶点。
对下面左侧图进行分析，我们从顶点 $1$ 出发到达顶点 $2$，可以发现如果步长为 $1,3,4,5,6,7$ 等都可以到达，但是步长为 $2$ 时无法到达。
如果走红色的路径从 $1$ 到 $2$，该路径长度为 $1$，那么 $3,5,6$ 等更大的奇数步长都能到达。因为大于 $1$ 的奇数数步长我们可以通过重复路径 $2-1-2$ 最终能够停留在目标顶点。如果走蓝色的路径从 $1$ 到 $2$，该路径长度为 $4$，那么 $6,8,10$ 等更大的偶数步长同样也能停留在目标顶点。
可将问题转换为求奇数步和偶数步的分层图最短路径问题。
### 解法一：分层建图
如上中间原图，我们可以采用分层建图方式，将原图拆分为 $2$ 层建图。第一层为偶数层，第二层为奇数层，连边时选择偶层连奇层，奇层连偶层。
由于是无权图可以跑 BFS 获取顶点 $1$ 到偶终点编号 $n$ 或奇终点编号 $2n$ 的最短路。根据 $L$ 的奇偶性选择判断 $L$ 是否大于等于该条最短路的长度，如果是则输出 `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;
}
```