寻找郑州网站优化公司,建设个人博客网站,购物网站建设的目的,做交网站题目: 样例解释#xff1a; 样例#1#xff1a; 编号为 1 的工人想生产第 1 阶段的零件#xff0c;需要编号为 2 的工人提供原材料。 编号为 2 的工人想生产第 1 阶段的零件#xff0c;需要编号为 1 和 3 的工人提供原材料。 编号为 3 的工人想生产第 1 阶段的零件#x…题目: 样例解释 样例#1 编号为 1 的工人想生产第 1 阶段的零件需要编号为 2 的工人提供原材料。 编号为 2 的工人想生产第 1 阶段的零件需要编号为 1 和 3 的工人提供原材料。 编号为 3 的工人想生产第 1 阶段的零件需要编号为 2 的工人提供原材料。 编号为 1 的工人想生产第 2 阶段的零件需要编号为 2 的工人生产第 1 阶段的零件需要为编号 1 和 3 的工人提供原材料。 编号为 2 的工人想生产第 2 阶段的零件需要编号为 1 和 3 的工人生产第 1 阶段的零件他/她们都需要编号为 2 的工人提供原材料。 编号为 3 的工人想生产第 2 阶段的零件需要编号为 2 的工人生产第 1 阶段的零件需要编号为 1 和 3 的工人提供原材料。 样例#2 编号为 1 的工人想生产第 1 阶段的零件需要编号为 2 和 5 的工人提供原材料。 编号为 1 的工人想生产第 2 阶段的零件需要编号为 2 和 5 的工人生产第 1 阶段的零件需要编号为 1,3,4 的工人提供原材料。 编号为 1 的工人想生产第 3 阶段的零件需要编号为 2 和 5 的工人生产第 2 阶段的零件需要编号为 1,3,4 的工人生产第 1 阶段的零件需要编号为 2,3,4,5 的工人提供原材料。 编号为 1 的工人想生产第 4 阶段的零件需要编号为 2 和 5 的工人生产第 3 阶段的零件需要编号为 1,3,4 的工人生产第 2 阶段的零件需要编号为 2,3,4,5 的工人生产第 1 阶段的零件需要全部工人提供原材料。 编号为 1 的工人想生产第 5 阶段的零件需要编号为 2 和 5 的工人生产第 4 阶段的零件需要编号为 1,3,4 的工人生产第 3 阶段的零件需要编号为 2,3,4,5 的工人生产 第 2 阶段的零件需要全部工人生产第 1 阶段的零件需要全部工人提供原材料。 代码140-60分算法
思路 设求第3点为第3阶段时点1是否需要提供原材料。 【3,3】 【2,2】【4,2】 【2,2】 【1,1】【3,1】 【4,2】 【3,1】【5,1】 【1,1】 【2,0】【5,0】 【3,1】 【2,0】【4,0】 【5,1】 【1,0】【4,0】 # 此处1需要提供原材料 比较容易想到对于每个询问进行暴搜若点1为0则Yes 时间复杂度很高必然超时。 #include bits/stdc.h
using namespace std;const int MAXN1005;
int vex[MAXN],k,n,m,q;
struct edge {int u,v,next;
}e[MAXN*2];int vis[MAXN][MAXN];void add(int u,int v){k;e[k].uu;e[k].vv;e[k].nextvex[u];vex[u]k;
}void dfs(int u,int s){if(s-1||vis[u][s]) return;vis[u][s]1;for(int ivex[u];i;ie[i].next){int ve[i].v;dfs(v,s-1);}return;
}int main(){cinnmq;while(m--){int u,v;cinuv;add(u,v);add(v,u);}while(q--){int u,L;memset(vis,0,sizeof(vis));cinuL;dfs(u,L);if(vis[1][0]) coutYesendl;else coutNoendl;}return 0;
} 代码2满分算法
思路 观察发现由于1-2的路径长度为1只要点2的阶段为奇数则点1一定要提供原材料1-2-1-2-...) 观察发现由于1-2-3的路径长度为2只要点3的阶段为偶数则点1一定要提供原材料 从1到v路径很多长度不尽相同。如果1到v的路径长度存在4时v在阶段4、6、8、10…时1肯定可以为0。当v的路径长度存在3时v在3、5、7、9…阶段1肯定可以为0。 因此要求的就是1到v的最短奇数路径和最短偶数路径。 若v的阶段为偶数x存在v的最短偶数路径y满足xy1即可为0。 若v的阶段为奇数x存在v的最短奇数路径y满足xy1即可为0。 设dis[v][0]为1到v的最短偶数路径设dis[v][1]为1到v的最短奇数路径 则有 dis[v][0] min(dis[v][0],dis[u][1]1) dis[v][1] min(dis[v][1],dis[u][0]1) 对于初始点1dis[1][0]显然等于0dis[1][1]显然不可能设为无穷大。 代码
#include bits/stdc.h
using namespace std;const int MAXN1e55;
int vex[MAXN],k,n,m,q;
struct edge {int u,v,next;
} e[MAXN*2];int vis[MAXN][2],dis[MAXN][2],que[MAXN*10],q2[MAXN*10],head,rear;void add(int u,int v) {k;e[k].uu;e[k].vv;e[k].nextvex[u];vex[u]k;
}void SPFA() {for(int i1; in; i) dis[i][0]dis[i][1]1e9;dis[1][0]0;head1;rear0;que[rear]1;while(headrear) {int uque[head];int tq2[head];head;vis[u][t]0;for(int ivex[u]; i; ie[i].next) {int ve[i].v;if(dis[v][0]dis[u][1]1) {dis[v][0]dis[u][1]1;if(!vis[v][0]) {vis[v][0]1;que[rear]v;q2[rear]0;}}if(dis[v][1]dis[u][0]1) {dis[v][1]dis[u][0]1;if(!vis[v][1]) {vis[v][1]1;que[rear]v;q2[rear]1;}}}}return;
}int main() {freopen(work.in,r,stdin);freopen(work.out,w,stdout);cinnmq;while(m--) {int u,v;cinuv;add(u,v);add(v,u);}SPFA();if(vex[1]0) dis[1][0]1e9; //补丁若1点没有连接边则1的偶数路径没有。while(q--) {int u,L;cinuL;if(Ldis[u][L%2]) coutYesendl;else coutNoendl;}return 0;
}
