企业官网建设流程全解析

网站seo优化心得,建设工程教育网校,电子商城前端模板,百度舆情系统题目名称#xff1a;强迫症冒险家的任务清单题目背景在广阔的“代码大陆”上#xff0c;有一位著名的冒险家。他虽然勇猛无双#xff0c;但有一个让旁人无法理解的习惯——严重的强迫症。冒险公会发布了N个委托任务#xff0c;编号从1到N。这些任务之间往往存在逻辑关联强迫症冒险家的任务清单题目背景在广阔的“代码大陆”上有一位著名的冒险家。他虽然勇猛无双但有一个让旁人无法理解的习惯——严重的强迫症。冒险公会发布了N个委托任务编号从1到N。这些任务之间往往存在逻辑关联比如“想去屠龙任务B必须先找到屠龙宝刀任务A”。也就是说某些任务必须在另一个任务完成后才能开始。这位冒险家做任务有两个原则绝对遵守规则如果任务U是任务V的前置条件他一定先完成U再去挑战V。编号强迫症当他手头有多个“当前立刻就能做”的任务时他一定会优先选择编号最小的那一个去执行。请你帮这位强迫症冒险家制定一份详细的任务执行顺序表。题目描述给定一个包含N个任务的清单以及M条前置关系规则。每条规则描述为u v表示任务u必须在任务v之前完成。请输出满足上述所有条件且符合冒险家“编号优先”习惯的任务执行序列。题目保证给出的关系网是有向无环图即一定存在可行解。输入格式第一行包含两个整数N, M分别表示任务的总数量和前置规则的数量。接下来M行每行包含两个整数u, v表示任务u是任务v的前置任务。输出格式一行包含N个整数表示冒险家完成任务的顺序整数之间用空格隔开。输入输出样例输入 #14 3 1 2 2 3 4 2输出 #11 4 2 3样例解释任务关系1-2, 4-2, 2-3。一开始任务1和任务4都没有前置条件都可以做。根据“编号强迫症”冒险家选择更小的1。做完1之后当前能做的只有4因为2还需要4完成才能解锁。冒险家做4。此时1和4都做完了任务2解锁。冒险家做2。做完2任务3解锁。冒险家做3。最终顺序1 4 2 3。数据范围2n100000m1000001u, vn, u!v1. 问题抽象与分析核心模型这个问题本质上是一个有向无环图DAG的拓扑排序问题节点代表任务。有向边u-v代表u是v的前置条件。拓扑序列一个线性的执行顺序满足所有依赖关系。为什么普通的拓扑排序不行普通的Kahn算法基于入度的拓扑排序使用的是queue普通队列。在普通队列中如果同时有任务1和任务4解锁了入度为 0谁先入队谁就先出来。这无法保证“优先做编号最小的任务”。举个例子假设任务1和4同时没有前置条件。普通队列可能输出4-1 ...题目要求必须输出1-4 ...解决方案优先队列为了满足“强迫症”要求字典序最小我们需要把普通的先进先出队列换成小根堆。容器选择priority_queue。排序规则greaterint从小到大。逻辑每次从堆里弹出的一定是当前所有入度为0的节点中编号最小的那个。2. 输入输出格式输入格式第一行输入两个整数n, m表示任务数量和前置规则数量。接下来m行每行两个整数u, v表示任务u必须在任务v之前完成。输出格式一行n个整数表示冒险家做任务的顺序。样例输入4 3 1 2 2 3 4 2(解释1-2, 4-2, 2-3。一开始1和4都没前置但1比4小所以先做1再做4解锁2最后3)样例输出1 4 2 33. 完整代码//字典序最小拓扑序 #include iostream #include vector #include queue using namespace std; int n,m; //默认大根堆需要修改为小根堆 priority_queueint,vectorint,greaterint q; vectorint edge[10010]; int d[10010];//记录每个点的入度 int l[10010];//记录拓扑序列 void tuopu(){ //将所有入度为0的点入队 for(int i1;in;i) if(d[i]0) q.push(i); int tot0;//记录l数组元素个数 while(!q.empty()){ int xq.top();//访问队首元素 q.pop();//队首出队 l[tot]x; for(auto y:edge[x]){//遍历所有以x为起点的边的终点y 然后把边删了 d[y]--;//边删了 y入度减一 if(d[y]0) q.push(y);//如果入度为0 就入队 } } for(int i1;itot;i) coutl[i] ; } int main(){ cinnm; //vector邻接表存图 for(int i1;im;i){ int u,v; cinuv; edge[u].push_back(v); d[v]; } tuopu();//拓扑排序 return 0; }4. 复杂度分析时间复杂度O(NMlogN)。我们需要遍历图中的所有点和边基础是O(NM)。但是每次节点入队和出队的操作是基于堆的复杂度为log(当前队列大小)。最坏情况下比如所有点一开始都入度为0复杂度会上升到O(NlogN)。空间复杂度O(NM)。主要消耗在邻接表edge存储边以及入度数组d。5. 总结这道题是拓扑排序的变种。如果是判断是否有环用普通队列、栈、甚至数组模拟都可以。如果是求任意一个拓扑序普通队列最快。如果是求字典序最小/最大的拓扑序必须使用优先队列堆。