aoe网完成工程的最短时间

aoe网完成工程的最短时间是26天。

一、在现代化管理中，人们常用有向图来描述和分析一项工程的计划和实施过程，一个工程常被分为多个小的子工程，这些子工程被称为活动（Activity)，在带权有向图中若以顶点表示事件，有向边表示活动，边上的权值表示该活动持续的时间，这样的图简称为AOE网。

二、关键术语：

1、路径长度：路径上各活动持续时间的总和（即路径上所有权之和）。

2、完成工程的最短时间：从工程开始点（源点）到完成点（汇点）的最短路径称为完成工程的最短时间。

3、关键路径：路径长度最长的路径称为关键路径。

三、注意事项：

1、生成树和最小生成树有许多重要的应用。例如：要在n个城市之间铺设光缆，主要目标是要使这n个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

2、拓扑排序主要解决的是一个工程能否顺利进行的问题。

3、关键路径是解决工程完成需要的最短时间问题。

4、最短路径用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。

5、Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

数据结构部分课程设计题目 题目一：运动会分数据统计问题描述：参加运动会的n个学校编号为1~n，比赛分成m个男子项目和w个女子项目，项目编号分别为1~m和m+1~m+w。有些项目取前五名，得分依次为6，4，3，2，1；有些项目取前三名，得分依次为4，2，1。写一程序产生各学校的成绩单（包括各校所取得的每项成绩的项目号、成绩、姓名和得分）和团体总分报表（包括校号、男子团体总分、女子团体总分和团体总分）。基本要求：参阅数据结构题集79页题目二：编写一个文本编辑器(记事本) 问题描述：要有文本编辑器的基本功能，如打开、编辑、保存等。基本要求 ：1．要制作字符形式的菜单．2．不同的功能使用不同的函数实现．3．对程序进行必要的注释．题目三：停车场管理问题问题描述：设停车场是一个可停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在南端，最先到达的第一辆车停放在停车场的最北端），若停车场内已停了n辆汽车，则后来的汽车只能在门外的通道上等候，一旦有车开走，收排在通道上的第一辆车即可开入；当停车场内每辆车要离开时，在它之后进入的车辆必须先退出停车场为其让路，待该辆车开出大门，其他车辆再按原次序进入停车场，每辆停放在停车场的车在它离开停车场时必须按它停留在停车场内的时间长短交纳停车费。试为停车场编写按上述要求进行管理的模拟程序。基本要求：参阅数据结构题集96页。 题目四： 图书管理 问题描述：图书管理基本业务活动包括对一本书的采编入库、清除库存、借阅和归还等等。将上述业务活动借助于计算机系统完成。基本要求：参阅数据结构题集167页 题目五：关键路径问题问题描述：设计一个程序求出完成整项工程至少需要多少时间以及整项工程中的关键活动。基本要求：1、对一个描述工程的AOE网，应判断其是否能够顺利进行。2、若该工程能顺利进行，输出完成整项工程至少需要多少时间，以及每一个关键活动所依附的两个顶点、最早发生时间、最迟发生时间。 题目六：任意长的整数加法问题描述：设计一个程序实现两个任意长的整数的求和运算。基本要求：利用双向循环链表，设计一个实现任意长的整数进行加法运算的演示程序。要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，0000题目七：哈夫曼编码译码器问题描述：打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，对每一个字符进行编码，编码完成后再对其编码进行译码。 题目八：交通咨询模拟问题描述：建立一个模拟的交通网络（用有向网来表示），编程实现从某个城市出发到另一个城市所需的最短的时间及路径。题目九：车厢调度问题描述：假设停在铁路调度站（如数据结构教材图31（b）所示）入口处的车厢序列的编号一次为1，2，3，…，n。设计一个程序，求出所有可能由此输出的长度为n的车厢序列。题目十：表达式求值问题描述：设计一个程序求任意一个浮点数表达式的计算结果。 题目十一：串的查找和替换问题描述：打开一篇英文文章，在该文章中找出所有给定的单词，然后对所有给定的单词替换为另外一个单词，再存盘。 题目十二：约瑟夫环问题描述：编号为1，2… n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。一开始任选一个正整数作为报数的上限值m，从第一个人开始按顺时针方向自1开始顺序报数，报到m时停止报数，报m的人出列，将他的密码作为新的m值，从他的顺时针方向上的下一个开始重新从1报数，如此下去，直至所有人全部出列为止，设计一个程序求出出列顺序。 基本要求：1、利用单循环链表作为存储结构模拟此过程；2、键盘输入总人数、初始报数上限值m及各人密码；
3、按照出列顺序输出各人的编号。 题目十三：构造可以使n个城市连接的最小生成树
问题描述：给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。
基本要求：1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。2、表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）3、最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。 题目十四：哈希表的设计与实现 问题描述： 设计哈希表实现电话号码查询系统。
基本要求：1、设每个记录有下列数据项：电话号码、用户名、地址；2、从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表；
3、采用再哈希法解决冲突；4、查找并显示给定电话号码的记录；5、查找并显示给定用户名的记录。
6、在哈希函数确定的前提下，尝试各种不同类型处理冲突的方法（至少两种），考察平均查找长度的变化。 题目十五：构造01串
问题描述：给定七个整数N,A,B,L,C,D,M;要求设计一个01串S=S(1)S(2)…S(N)。
基本要求：1、S(i)=0或S(i)=1,1≤i≤N;
2、对于S的任何连续长度为L的子串S(j)S(j+1)…S(j+L-1) ,(1≤j≤N-L+1),0的个数大于等于A且小于等于B;
3、对于S的任何连续长度为M的子串S(j)S(j+1)…S(j+M-1) , (1≤j≤N-M+1),0的个数大于等于C且小于等于D; 列如,N=6,A=1,B=2,L=3,C=1,D=1,M=2,则存在一个满足上述所有条件的01串 S=10101。

1． 输入e条弧，建立AOE-网的存储结构。
2． 拓扑排序，并求得ve[]。从源点V0出发，令ve[0]=0,按拓扑有序求其余各顶点的最早发生时间ve[i]。如果得到的拓扑有序序列中顶点个数小于网中顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤3。
3． 拓扑逆序，求得vl[]。从汇点Vn出发，令vl[n-1] = ve[n-1]，按逆拓扑有序求其余各顶点的最迟发生时间vl[i]。
4． 求得关键路径。根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开始时间l(s)。若某条弧满足条件e(s) = l(s)，则为关键活动。
为了能按逆序拓扑有序序列的顺序计算各个顶点的vl值，需记下在拓扑排序的过程中求得的拓扑有序序列，这就需要在拓扑排序算法中，增设一个栈，以记录拓扑有序序列，则在计算求得各顶点的ve值之后，从栈顶到栈底便为逆拓扑有序序列。

1、生成树和最小生成树有许多重要的应用。例如：要在n个城市之间铺设光缆，主要目标是要使这n个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同，因此另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。
2、拓扑排序主要解决的是一个工程能否顺利进行的问题。
3、关键路径是解决工程完成需要的最短时间问题。
4、最短路径用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
5、Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。

---