模型
给定一张包含 $n$ 个点和 $m$ 条边的无向图,再给定 $q$ 个询问:$a_i, L_i$,判断是否存在一条从1号点走到 $a_i$ 号点的恰好经过 $L$ 条边的路径。
算法
(最短路,BFS) $O(n + m + q)$
本题关键点:
如果存在一条长度是 $L$ 的路径,其中 $L > 0$,那么我们可以在其中任意一条边上来回走,就可以构造出来长度是 $L + 2, L + 4, L + 6, … $ 的路径。
因此当我们想判断是否存在长度是 $L$ 的路径时,只需判断是否存在长度小于等于 $L$,且奇偶性和 $L$ 相同的路径即可。
因此我们可以预处理出从1号点出发,到每个点长度为奇数的最短路径和长度为偶数的最短路径。
这里可以使用拆点技巧来构造新图,类似于DP中的状态机模型:
- 将原图中的每个点 $v$ 拆成两个新点:偶点$v_0$和奇点$v_1$;
- 将原图中的每条边 $(u, v)$ 拆成两条新边:$(u_0, v_1)$ 和 $(u_1, v_0)$;
那么在新图中从 $1$ 号点走到 $v_0$ 的所有路径,对应在原图中从 $1$ 号点走到 $v$ 的所有长度是偶数的路径;在新图中从 $1$ 号点走到 $v_1$ 的所有路径,对应在原图中从 $1$ 号点走到 $v$ 的所有长度是奇数的路径。
因此在新图上求出1号点到其他所有点的最短路径,即可求出在原图中从1号点到其他所有点的长度是奇数和偶数的最短路径。
由于所有边的长度为1,因此可以用BFS求最短路。
以上我们处理了 $L_i > 0$ 的情况,还需特判一下 $L_i == 0$ 的情况,$L_i == 0$ 表示一条边都不存在,即1号点与其他点均不连通,此时由于输入时 $L_i \ge 1$,因此直接输出"No"
即可。
时间复杂度
使用BFS求最短路的时间复杂度是 $(n + m)$;
判断每个查询操作的时间复杂度是 $O(1)$;
因此总时间复杂度是 $O(n + m + q)$。
C++ 代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 100010, M = 200010;
int n, m, query;
int h[N], e[M], ne[M], idx;
PII q[N * 2];
int dist[N][2];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void bfs()
{
memset(dist, 0x3f, sizeof dist);
int hh = 0, tt = 0;
q[0] = {1, 0};
dist[1][0] = 0;
while (hh <= tt)
{
PII t = q[hh ++ ];
int ver = t.first, type = t.second;
for (int i = h[ver]; ~i; i = ne[i])
{
int j = e[i];
if (dist[j][type ^ 1] > dist[ver][type] + 1)
{
dist[j][type ^ 1] = dist[ver][type] + 1;
q[ ++ tt] = {j, type ^ 1};
}
}
}
}
int main()
{
scanf("%d%d%d", &n, &m, &query);
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b), add(b, a);
}
bfs();
while (query -- )
{
int a, l;
scanf("%d%d", &a, &l);
if (a == 1 && h[1] == -1) puts("No");
else if (dist[a][l & 1] <= l) puts("Yes");
else puts("No");
}
return 0;
}
yls题目中好像说$L>1$所以好像不用特判边界条件(我把您的代码去掉特判试试发现可以A)
还有我想问$L=0$的实际意义是什么?按照题目中的解释就是
想要生产第L阶段(L=0那么不就是原材料?)
感觉怪怪的。。抛开这个题如果要特判在这行代码中
if (a == 1 && h[1] == -1) puts("No");
为什么需要a==1
呢?数据已加强,现在不特判边界会WA。这个特判表示:如果1号点与其他所有点不连通,那么如果想在1号点加工一个$L(L > 0)$ 阶段的零件,那么1号点是一定不需要提供原材料的。因为
dist[1][0]
等于0,所以如果用第二个判断,那么当 $L > 0$ 且是偶数时会判断成Yes
,这就错了。