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

· · 题解

P5663 [CSP-J2019] 加工零件

J 组特有的图论题目，主打一个好写不好想。

思路分析

一上来就分析一般情况确实困难，所以我们先想一些特殊情况。对于图来说，特殊情况容易想到是一棵树。于是我们去想假如这是以 1 为根结点的一棵树，怎么去做。

很容易就会发现，如果 1 到询问结点 u 的距离 d 如果是奇数，且制作的零件阶段数 L 也是一个大于 d 的奇数，则 1 就需要贡献材料。偶数也与上文类似。

为什么呢？感性证明一下：对于一个边两边的点，零件从一个点传出再传入，阶段数会 -2，因此只有当自己制作的零件阶段数是偶数时，零件最后传回自己的时候才是 0 阶段（即原材料）。推广一下就可以得到上面的结论。

那么如果是一个图呢？图的特点就是两点间的路径有多个。那么我们难道要对每条路径的长度奇偶性都做出判断吗？显然不用，我们只用关心最短的奇路径和最短的偶路径即可，因为更长的路径都已经被包含了。

所以做法就很简单了，从结点 1 出发跑奇偶最短路。询问点 u 做的零件阶段为 L 的时候如果这个点 L 对应的奇偶性的最短路 \le L，那么就需要提供，否则就不需要。

AC Code

代码使用的是 Dijkstra 最短路，由于本题边权都为 1，可以使用 BFS 求最短路，复杂度还会更优。

其实这样的思路有点类似于分层图，还可以去 CSP-J 2024 T4 看看分层图的应用。

#include <bits/stdc++.h>
using namespace std;
int n,m,Q;
struct edge{
    int to,nxt,w;
}e[200005];
int head[100005],tot;
inline void add(int u,int v,int w) {
    e[++tot].to = v;
    e[tot].nxt = head[u];
    e[tot].w = w;
    head[u] = tot;
}
struct node{
    int p,w;
    bool operator < (const node &x) const{
        return w > x.w;
    }
};
int dis[100005][2],f[100005][2];//把一个点的奇偶分开，可以理解为两个点。
priority_queue<node> q;
inline void dij(int s) {
    q.push({s,0});
    memset(dis,0x3f,sizeof(dis));
    dis[1][0]=0;//注意初始化只有偶最短路，自己到达自己路径长度为 0，因此只用初始化偶最短路。
    while(!q.empty()) {
        node t = q.top();
        q.pop();
        if (f[t.p][t.w%2]) continue;
        f[t.p][t.w%2] = 1;
        for (int i = head[t.p]; i; i = e[i].nxt) {
            int v = e[i].to,w = t.w+e[i].w;
            if (dis[v][w%2]>w) {
                dis[v][w%2] = w;
                q.push({v,w});
            }else if(dis[v][w%2]>w) {
                dis[v][w%2] = w;
                q.push({v,w});
            }
        }
    }
}
int main () {
    cin >> n >> m >> Q;
    for (int i = 1; i <= m; i++) {
        int u,v;
        cin >> u >> v;
        add(u,v,1);
        add(v,u,1);//双向边
    }
    dij(1);
    // for (int i = 1; i <= n; i++) {
    //  cout << dis[i][0] << ' ' << dis[i][1] << '\n'; 
    // }
    while(Q--) {
        int u,v;
        cin >> u >> v;
        if (dis[u][v%2] <= v) {//最短路如果大于 v 则一定不需要，因为在路径中途 v 就会减为 0。
            puts("Yes");
        }else{
            puts("No");
        }
    }
    return 0;
}