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

kradcigam · 2019-11-23 18:14:21 · 题解

博客园体验更佳

讲讲我的做法

确定做法

首先，看到这道题，我直接想到的是递归，于是复杂度就上天了，考虑最短路。

如何用最短路

首先，看一张图

我们该如何解决问题？

问题:3做5阶段的零件1要不要做呢？

其实，实质就是看3到1有没有长度为5的路径。

问题:3做7阶段的零件1要不要做呢？

其实，实质就是看3到1有没有长度为7的路径。

问题:3做6阶段的零件1要不要做呢？

其实，实质就是看3到1有没有长度为6的路径。

仔细思考这3个问题，我们会发现，如果3到1有长度为5的路径，那么3到1一定有长度为7的路径，但并不一定有长度为6的路径。

所以，我们要对每个点求一遍奇数路径，和偶数路径。

实现最短路

最短路的算法有很多，这道题最好用dijkstra，或bfs。

这道题的时限并不紧，并且dijkstra细节太多，我就来演示bfs实现的最短路

void bfw(){//我有一个好朋友叫bfw，所以我写bfs时，喜欢把函数名起为bfw
    memset(ji,0x3f,sizeof(ji));//奇数最短路径
    memset(ou,0x3f,sizeof(ou));//偶数最短路径
    queue<pair<int,int> >q;
    q.push(make_pair(1,0));
    ou[1]=0;
    while(q.size()){
        int x=q.front().first,y=q.front().second;
        for(int i=0;i<v[x].size();i++){
            if(y%2==1){//奇数+1=偶数
                if(y+1<ou[v[x][i]]){
                    ou[v[x][i]]=y+1;//更新答案
                    q.push(make_pair(v[x][i],y+1));
                }
            }else{//偶数+1=奇数
                if(y+1<ji[v[x][i]]){
                    ji[v[x][i]]=y+1;//更新答案
                    q.push(make_pair(v[x][i],y+1));
                }
            }
        }
        q.pop();
    }
}