题解 P5663 【加工零件【民间数据】】

· · 题解

题目链接

0.前记

考场上因为时间紧迫加上近视度数过深，代码敲成"YES"和"NO"，喜提0分的好成绩

1.思路

i.

从最简单的图开始

我们不难发现，对于1想做2n阶段时，就必须做2n,2n-2,...0阶段的零件，而此时2对应做的时2n-1,2n-3...1阶段

同样的，若1想做2n-1阶段时，就必须做2n-3...1阶段，2应该做2n-2,2n-4...0阶段

总而言之，对于第i个点而言，当它想做阶段L的零件

·如果L为偶数，且存在i走偶数步可以到1的方法，则Yes

·如果L为奇数，且存在i走奇数步可以到1的方法，则Yes

·若不满足以上两种情况，必No

ii.

同样找一个简单图

我们思考一个问题，如果1要做一个阶段1的零件，它该是Yes还是No呢

如果按照之前找到的奇偶来找，存在一条1-2-3-1的路径，它的长度为奇数3，那么应该是Yes

但是我们要想，1阶段刚走出去到2和3，2和3做0阶段之后，就没得再走下去了

毕竟没有-1阶段这种东西吗

那么我们得到第二个结论：

若L还不到i到1的最短路，那么也是No

我们把上面两种情况的结论合并一下：

记从i点走偶数步到1点的最短路为dis[i][0],走奇数步为dis[i][1]

·如果L为偶数，且dis[i][0]<=L则输出Yes

·如果L为奇数，且dis[i][1]<=L则输出Yes

·以上条件均不满足，输出No

那么我们就可以想到应该分奇偶两种跑最短路

2.实现细节

i.特殊情况

如果没有任何节点与1相连，那么无论如何都输出No

ii.算法选择

题解里有好多人用dij,spfa的，事实上在这题里面完全没有必要

我们发现由于每条边的长度都是1，也就是说后遍历到的绝对比前面遍历到的点的距离要远

直接搞一个队列bfs即可

每次找到一个点，判断一下之前同奇偶性的这个点走过没有，有过就舍弃，否则就入队尾

每个点保证最多奇偶各进一次，时间复杂度最满也是O(2n)

iii.常数优化（可无视，纯属卡常和压行癖好）

初始的时候直接令dis[i][0]=dis[i][1]=1e9+7，既可以当判断是否遍历过的数组，还可以作为记录距离的数组，如果无路直接判断1e9+7>L输出No

当然dis[1][0]=0

iv.异或的使用（又一个卡常和压行）

在代码中，我们用0代表偶数步的情况，1代表奇数步的情况

对于偶数步，我们再走一步就是奇数步了，即0转移到的是1

同理，1转移到的是0

因此我们可以用^1来转移，即0^1=1 1^1=0

3.代码

#include<cstdio>
#include<cctype>
const int maxn=1e5+5;
inline char nc()
{
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int R(){//快读，没错又是卡常 
    int r=0;char c=nc();
    while(!isdigit(c)) c=nc();
    while(isdigit(c)) r=(r<<1)+(r<<3)+(c^48),c=nc();
    return r;
}
int n,m,q,head[maxn],tot,dis[maxn][2],dl[maxn<<1][2];
//dl[i][0]:节点编号,dl[i][1]:所对应的情况是偶数还是奇数，对应0和1
//dis[i][0]:i点走偶数步到1的最短路,dis[i][1]同 
bool d;//判断节点1有无连边 
struct node{
    int to,next;
}edge[maxn<<1];
inline void add(int from,int to){
    edge[++tot].next=head[from];
    edge[tot].to=to;
    head[from]=tot;
    return ;
}
inline void work(){//bfs
    dl[1][0]=1;dl[1][1]=0;dis[1][0]=0;//入队加初始化 
    int l=0,r=1;
    while(l<r){
        l++;int k=dl[l][0];//k为当前遍历到的节点 
        for(register int i=head[k];i;i=edge[i].next){
            int u=edge[i].to;//u为下一个节点 
            if(dis[u][dl[l][1]^1]!=1e9+7) continue;//如果下一个节点的dl[l][1]^1走过，就不要走了 
            dis[u][dl[l][1]^1]=dis[k][dl[l][1]]+1;//覆盖dis 
            dl[++r][0]=u;dl[r][1]=dl[l][1]^1;//下一个节点入队 
        }
    }
}
int main(){
    n=R();m=R();q=R();
    for(register int i=1;i<=m;i++){
        int a=R(),b=R();
        add(a,b);add(b,a);
        if(a==1 || b==1) d=1;//只要1出现，就有连边 
    }
    for(register int i=1;i<=n;i++) dis[i][0]=dis[i][1]=1e9+7;//初始化 
    if(d) work();//1没连边就没有必要跑work了（也是为了卡常） 
    for(register int i=1;i<=q;i++){
        int a=R(),l=R();
        if(d && l>=dis[a][l&1]) puts("Yes");//满足条件就输出Yes
        else puts("No");//否则输出No 
    }
    return 0;
}

4.运行效果

5.后记

本题的思维难度还是有那么一点的，但是一旦想到，问题就可以迎刃而解

Finally，谢谢大家

更好的阅读体验