题解 P5663
empty_zhm
·
·
题解
这是一个 BFS 的算法
最短路楼上大佬讲得好清楚的QwQ
这个题目当然可以用最短路解决
但我当时不会怎么办
但是这个题的边长固定为1，所以我就想到了用bfs去做。
在一副图中，从a点走L步,允许重复走，可不可以走到点1。
有了这个（简单易懂）的题目，那么我们就可以往下思考了。
首先先讨论下，从点a，有什么情况可以走到点1。
一、在无环图当中
1、可以直接走到点1:
比如图1：
我们用有序数对(a,b)，来代表在a点时还剩b步没走。
如果初始状态是(3,2)。接下来是(2,1)\ (1,0)，刚好传过去。
2、当走到点1时，若还有几步未走，便来回走直到剩余步数为0：
如果初始状态是(3,4)。就可以有(2,3)\ (1,2)\ (2,1)\ (1,0)。
总结：
在无环图中，当我们可以求得最短路长度s。当有s\le L且(s\ xor\ L)\!\mod 2=0时，可以从点a刚好用L步走到点1。
二、但题目很清楚的描述了：这个题目不排除有环图QwQ
所以这就引出了一个新的问题。
如果，我们有一个奇数长度的环怎么办？
见图2：(找不到图了只好手绘QwQ）
3、当预见最短路径奇偶性与L不相同时，我们可以选择绕一个奇数环走一圈来改变自己剩余路径的奇偶值。
（当a点与1点位于同一奇数环时，换一个方向即可，不一定要绕一整圈）
如果初始状态是(4,7)，显然与最短路径长度奇偶性不符，但依然有解(3,6)\ (2,5)\ (1,4)\ (2,3)...(1,0)。
总结
当最短路径s与L奇偶性不同时，我们可以尝试寻找与其奇偶性不同的路径中最短的s_0。当s_0\le L时，可以从点a刚好用L步走到点1。
总体总结
分别求得点a到点1最短的偶数长度的路径s_0和最短的奇数长度的路径s_1（但可能两者中有一者不存在）
当存在s_0和s_1时：
## 具体做法
先 BFS 预处理出每个点和1点间的奇偶最短路径的长度。最后在输入时进行如上的判断就好了。（~~是不是很简单呢~~）
但是没有AC，为什么呢？
若点$a$与点1并不联通，则$s_0$和$s_1$都不存在，则绝没有解。
# 接下来上代码。
```cpp
#include<bits/stdc++.h>
#define N 100010
using namespace std;
struct node
{
int to;
node *last,*next;
node()
{
last=next=NULL;
to=-1;
}
}*_A[N];//链式前向星
struct data
{
int deep,i;
data(){deep=i=0;}
};//deep指深度（其实就是路径长度）,i指当前节点。
int A[N][2],n,L,m,B[N];
/*A[i][1],A[i][0]分别表示第i个点与1点的奇偶最短距离*/
queue <data> _B;
void add(int a,int b)
{
if(_A[a]==NULL)/*如果是第一次连边的话，
如果要调用_A[a]的话 百分之一百亿会出错(千空句式)*/
{
_A[a]=new(node);
_A[a]->to=b;//同下
return;
}
node *p=new(node);
p->to=b;//表示指向
p->next=_A[a]->next;
_A[a]->next=p;
}//简单的链式前向星的连边
void bfs()
{
while(!_B.empty())
{
int r=_B.front().i,_i=_B.front().deep;
for(node *i=_A[r];i!=NULL;i=i->next)//遍历以r为开始端的边的标准打法(bushi)
{
int a=i->to;
if(B[a]>1||a==-1) continue;
/*如果B[a]已经入队两次
(代表奇偶最短路都已经记录完了)
或者B[a]没有后续值就不入队了。*/
if((A[a][B[a]-1]&1) == (_i&1) || !B[a])//如果这次路径与上次的奇偶性不同或者是没有入过队,就入队。否则绝不是最短路径就不入队。
{
A[a][B[a]]=_i+1;//记录路径长度
B[a]++;//记录入队次数
data p;
p.deep=_i+1;
p.i=a;
_B.push(p);
}//基本入队操作
}
_B.pop();
}
}
int main()
{
memset(A,0x7f,sizeof(A));//初始化极大值,以免没有连上的也奇偶判断
cin >> n >> m >> L;
for(int i=1;i<=m;i++)
{
int a,b;
cin >> a >> b;
add(a,b);
add(b,a);//有人云:"无向图就是双向的有向图"
}
A[1][0]=0;
B[1]=1;
//初始化
data check;
check.deep=0,check.i=1;
_B.push(check);
bfs();
for(int i=1;i<=L;i++)
{
int a,b;
cin >> a >> b;
if((A[a][0]<=b) && ((b^A[a][0])%2)==0) puts("Yes");
else if((A[a][1]<=b) && ((b^A[a][1])%2)==0) puts("Yes");
else puts("No");//否则输出No
}
}
```
（我原来题解写得好渣QwQ，我哭了）