洛谷 P5663 加工零件

题目传送门

解题思路:

最暴力的做法:

bfs模拟,每次将一个阶段的所有点拿出来,将其所有直连的点都放进队列,知道本阶段结束,最后看1号点会不会在最后一个阶段被放入队列.(洛谷数据40分)

优化了一下代码:

上面的做法我用了两个队列,发现代码可以优化一下,用一个队列.(洛谷数据55分).

正解:

对于一个点,如果它加工的零件是偶数阶段,则在一定范围内与它偶数距离的点都要提供原料.

对于一个点,如果它加工的零件是奇数阶段,则在一定范围内与它奇数距离的点都要提供原料.

那么这个一定范围是多少呢?

就是小于等于这个点加工阶段大小的范围.

代码:

 #include<iostream>

 #include<cstdio>

 #include<vector>

 #include<cstring>

 #include<queue>

 using namespace std;

 int n,m,qq,x,y;

 bool vis[];

 queue<int> q,q1;

 struct kkk{

     vector<int > a;

     int len;

 }e[];

 inline void solve() {

     int id,s;

     scanf("%d%d",&id,&s);

     memset(vis,,sizeof(vis));

     while(!q.empty()) q.pop();

     while(!q1.empty()) q1.pop();

     q.push(id);

     vis[id] = ;

     while(s--) {

         while(!q.empty()) {

             int v = q.front();

             q.pop();

             vis[v] = ;

             if(e[v].len != )

                 for(int i = ;i < e[v].len; i++)

                     q1.push(e[v].a[i]);

         }

         while(!q1.empty()) {

             int ee = q1.front();

             vis[ee] = ;

             q1.pop();

             q.push(ee);

         }

     }

     if(vis[]) printf("Yes\n");

     else printf("No\n");

 }

 int main() {

     scanf("%d%d%d",&n,&m,&qq);

     for(int i = ;i <= n; i++)

         e[i].len = ;

     for(int i = ;i <= m; i++) {

         scanf("%d%d",&x,&y);

         e[x].len++;e[y].len++;

         e[x].a.push_back(y);

         e[y].a.push_back(x);

     }

     for(int i = ;i <= qq; i++)

         solve();

     return ;

 }

最暴力的做法

 #include<iostream>

 #include<cstdio>

 #include<vector>

 #include<cstring>

 #include<queue>

 using namespace std;

 int n,m,qq,x,y;

 bool vis[];

 queue<int> q;

 struct kkk{

     vector<int > a;

     int len;

 }e[];

 inline void solve() {

     int id,s;

     scanf("%d%d",&id,&s);

     memset(vis,,sizeof(vis));

     while(!q.empty()) q.pop();

     q.push(id);

     vis[id] = ;

     while(s--) {

         int u = q.size();

         for(int i = ;i <= u; i++) {

             int v = q.front();

             q.pop();

             vis[v] = ;

             if(e[v].len != )

                 for(int i = ;i < e[v].len; i++) {

                     if(vis[e[v].a[i]]) continue;

                     q.push(e[v].a[i]);

                     vis[e[v].a[i]] = ;

                 }

         }

     }

     if(vis[]) printf("Yes\n");

     else printf("No\n");

 }

 int main() {

     scanf("%d%d%d",&n,&m,&qq);

     for(int i = ;i <= n; i++)

         e[i].len = ;

     for(int i = ;i <= m; i++) {

         scanf("%d%d",&x,&y);

         e[x].len++;e[y].len++;

         e[x].a.push_back(y);

         e[y].a.push_back(x);

     }

     for(int i = ;i <= qq; i++)

         solve();

     return ;

 }

优化暴力的代码

 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<cstring>

 using namespace std;

 int n,m,qq,head[],ji[],ou[];

 bool flag;

 struct kkk{

     int to,next;

 }e[];

 int tot;

 queue<int> q;

 inline void add(int x,int y) {

     e[++tot].to = y;

     e[tot].next = head[x];

     head[x] = tot;

 }

 inline void spfa() {

     ou[] = ;

     q.push();

     while(!q.empty()) {

         int s = q.front();

         q.pop();

         for(int i = head[s];i != ; i = e[i].next) {

             int t = e[i].to,jv = ji[t],ov = ou[t];

             ji[t] = min(ji[t],ou[s] + );//更新奇数最短路

             ou[t] = min(ou[t],ji[s] + );//更新偶数最短路

             if(jv != ji[t] || ov != ou[t])

                 q.push(t);

         }

     }

 }

 int main() {

     scanf("%d%d%d",&n,&m,&qq);

     for(int i = ;i <= m; i++) {

         int x,y;

         scanf("%d%d",&x,&y);

         add(x,y);

         add(y,x);

         if(y ==  || x == ) flag = ;

     }

     memset(ji,0x3f3f,sizeof(ji));

     memset(ou,0x3f3f,sizeof(ou));

     spfa();

     for(int i = ;i <= qq; i++) {

         int id,jd;

         scanf("%d%d",&id,&jd);

         if(!flag) {

             printf("No\n");

             continue;

         }

         if(jd %  ==  && ji[id] <= jd) {

             printf("Yes\n");

             continue;

         }

         if(jd %  ==  && ou[id] <= jd) {

             printf("Yes\n");

             continue;

         }

         printf("No\n");

     }

     return ;

 }

正解

//CSP-J2019 T4