企业官网建设流程全解析

企业网站 备案 网站名称,wordpress 商品展示插件,wordpress 最值得购买 主题,手机更新wordpress信奥赛C提高组csp-s之拓扑排序#xff08;案例实践#xff09; 杂务 (Job Processing) 问题描述 有n个杂务需要完成#xff0c;某些杂务必须在另一些杂务完成之后才能开始。每个杂务都有完成所需的时间。求完成所有杂务所需的最短时间。 输入格式 第一行#xff1a;整数…信奥赛C提高组csp-s之拓扑排序案例实践杂务 (Job Processing)问题描述有n个杂务需要完成某些杂务必须在另一些杂务完成之后才能开始。每个杂务都有完成所需的时间。求完成所有杂务所需的最短时间。输入格式第一行整数n (1 ≤ n ≤ 10,000)表示杂务数量接下来n行每行描述一个杂务第一个数该杂务的编号第二个数完成该杂务所需时间后面的数该杂务的前驱杂务编号列表以0结束输出格式一个整数表示完成所有杂务所需的最短时间题目分析本题要求计算完成所有杂务的最短时间。杂务之间存在依赖关系某些杂务必须在另一些完成后才能开始但互不依赖的杂务可以同时进行。由于依赖关系仅存在于编号较小的杂务中整个依赖图是一个有向无环图DAG因此可以通过拓扑排序求解。解题思路问题建模将每个杂务视为图中的节点依赖关系视为有向边从准备工作指向当前杂务。同时记录每个杂务的耗时和入度依赖的前驱数量。拓扑排序从入度为0的节点无依赖的杂务开始处理逐步处理依赖这些节点的后续杂务。动态更新最早完成时间对于每个杂务其最早完成时间等于所有前驱节点最早完成时间的最大值加上当前杂务的耗时。计算全局最大值所有杂务的最早完成时间中的最大值即为完成所有杂务的最短时间。代码实现#includebits/stdc.husingnamespacestd;constintN10010;intn;vectorinta[N];// 邻接表a[u]存储所有u指向的后继节点u完成后才能进行的任务intd[N];// 入度数组d[i]表示杂务i的入度依赖的前驱数量intt[N];// t[i]表示杂务i的耗时intmint[N];// mint[i]表示杂务i的最早完成时间intmain(){cinn;// 读取n个杂务的数据for(inti1;in;i){intid,cost,pre;cinidcost;// 读入杂务序号和耗时t[id]cost;// 存储耗时// 读取该杂务的所有前驱准备工作以0结束while(cinprepre!0){a[pre].push_back(id);// 添加依赖关系pre - idd[id];// id的入度增加}}queueintq;// 用于拓扑排序的队列// 初始化将所有入度为0的杂务加入队列for(inti1;in;i){if(d[i]0){q.push(i);mint[i]t[i];// 无依赖的杂务最早完成时间即自身耗时}}intans0;// 记录所有杂务的最早完成时间中的最大值// 拓扑排序while(!q.empty()){intuq.front();// 取出一个入度为0的节点q.pop();// 更新全局最大完成时间ansmax(ans,mint[u]);// 遍历u的所有后继节点for(intv:a[u]){// 更新v的最早完成时间必须等所有前驱完成取最大值mint[v]max(mint[v],mint[u]t[v]);// 减少v的入度因为u已完成d[v]--;// 如果v的入度变为0加入队列if(d[v]0){q.push(v);}}}coutansendl;// 输出所有杂务完成的最短时间return0;}功能分析数据存储a[N]邻接表存储依赖关系有向边。d[N]记录每个节点的入度前驱数量。t[N]记录每个杂务的耗时。mint[N]动态记录每个杂务的最早完成时间。拓扑排序流程初始化将所有入度为0的杂务加入队列并初始化其最早完成时间。队列处理取出队首节点用其最早完成时间更新全局答案。遍历该节点的所有后继节点更新后继节点的最早完成时间取当前值与新路径值的最大值。减少后继节点的入度若入度为0则加入队列。关键点最早完成时间计算每个杂务的最早完成时间取决于所有前驱完成时间的最大值因为必须等待所有准备工作完成。并行处理由于不依赖的杂务可以同时进行全局答案只需取所有杂务完成时间的最大值。该算法时间复杂度为O(N E)其中N为杂务数量E为依赖边数量满足题目要求。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}一、CSP信奥赛C通关学习视频课C语法基础C语法进阶C算法C数据结构CSP信奥赛数学CSP信奥赛STL二、CSP信奥赛C竞赛拿奖视频课信奥赛csp-j初赛高频考点解析CSP信奥赛C复赛集训课12大高频考点专题集训三、csp高频考点知识详解及案例实践CSP信奥赛C之动态规划CSP信奥赛C之标准模板库STL信奥赛C提高组csp-s知识详解及案例实践四、考级、竞赛刷题题单及题解GESP C考级真题题解CSP信奥赛C初赛及复赛高频考点真题解析CSP信奥赛C一等奖通关刷题题单及题解详细内容1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转CSP信奥赛C一等奖通关刷题题单及题解持续更新https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}