08-图9 关键活动 (30 分)假定一个工程项目由一组子任务构成子任务之间有的可以并行执行有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程各门课程可以看成是子任务。有些课程可以同时开设比如英语和C程序设计它们没有必须先修哪门的约束有些课程则不可以同时开设因为它们有先后的依赖关系比如C程序设计和数据结构两门课必须先学习前者。但是需要注意的是对一组子任务并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B子任务B依赖于子任务C子任务C又依赖于子任务A”那么这三个任务哪个都不能先执行这就是一个不可行的方案。任务调度问题中如果还给出了完成每个子任务需要的时间则我们可以算出完成整个工程需要的最短时间。在这些子任务中有些任务即使推迟几天完成也不会影响全局的工期但是有些任务必须准时完成否则整个项目的工期就要因此延误这种任务就叫“关键活动”。请编写程序判定一个给定的工程项目的任务调度是否可行如果该调度方案可行则计算完成整个工程项目需要的最短时间并输出所有的关键活动。输入格式:输入第1行给出两个正整数N(≤100)和M其中N是任务交接点即衔接相互依赖的两个子任务的节点例如若任务2要在任务1完成后才开始则两任务之间必有一个交接点的数量。交接点按1N编号M是子任务的数量依次编号为1M。随后M行每行给出了3个正整数分别是该任务开始和完成涉及的交接点编号以及该任务所需的时间整数间用空格分隔。输出格式:如果任务调度不可行则输出0否则第1行输出完成整个工程项目需要的时间第2行开始输出所有关键活动每个关键活动占一行按格式“V-W”输出其中V和W为该任务开始和完成涉及的交接点编号。关键活动输出的顺序规则是任务开始的交接点编号小者优先起点编号相同时与输入时任务的顺序相反。输入样例: 7 8 1 2 4 1 3 3 2 4 5 3 4 3 4 5 1 4 6 6 5 7 5 6 7 2 输出样例: 17 1-2 2-4 4-6 6-7代码#includeiostream #includequeue #includestack #includemap #includeutility using namespace std; #define Maxsize 101 #define Inf 65535 typedef int Vertex; typedef int WeightType; typedef struct LNode* PtrToLNode; typedef struct VNode { PtrToLNode FirstEdge; WeightType Earliest; WeightType Latest; int InDegree; VNode():FirstEdge(NULL),Earliest(0),Latest(Inf), InDegree(0){} }PtrToLNodeArr[Maxsize]; struct LNode { Vertex V; WeightType Weight; WeightType Delay; PtrToLNode Next; }; typedef struct GraphNode* Graph; struct GraphNode { int Nv; int Ne; PtrToLNodeArr heads; }; Graph BuildGraph(int N, int M) { Graph G new GraphNode; G-Nv N; G-Ne M; Vertex v1, v2; WeightType W; PtrToLNode tmp; for (int i 1; i M; i) { cin v1 v2 W; tmp new LNode; tmp-V v2; tmp-Weight W; tmp-Next G-heads[v1].FirstEdge; G-heads[v1].FirstEdge tmp; } return G; } /*以上为建图*/ /*拓扑排序*/ void InDegreeCount(Graph G) { /*统计入度*/ PtrToLNode tmp; Vertex V,W; for (V 1; V G-Nv; V) { tmp G-heads[V].FirstEdge; while (tmp ! NULL) { W tmp-V; G-heads[W].InDegree; tmp tmp-Next; } } } int TopSorting(Graph G) { InDegreeCount(G); queueVertex q; stackVertex s; Vertex V,W;//点对象 int res 0;//结果 PtrToLNode tmp;//边对象指针 for (Vertex V 1; V G-Nv; V) {//将入度为0的入队列 if (G-heads[V].InDegree 0) { q.push(V); } } int Vcount 0;//用来统计拓扑排序是否失效 while (q.empty() ! 1) { V q.front(); s.push(V); q.pop();//弹出V Vcount; for (tmp G-heads[V].FirstEdge; tmp ! NULL; tmp tmp-Next) {//对V的邻接点进行更新 W tmp-V; G-heads[W].InDegree--;//更新入度 if (G-heads[W].InDegree 0) { q.push(W); } if (G-heads[V].Earliest tmp-Weight G-heads[W].Earliest) { G-heads[W].Earliest G-heads[V].Earliest tmp-Weight;//更新W的最早时间 } } } /*判断拓扑排序是否失效没有失效才继续往下做*/ if (Vcount ! G-Nv) { res 0; return res; } InDegreeCount(G);//重新更新一下入度,可不做这一步不影响结果 int MaxTime 0; for (Vertex Vtmp 1; Vtmp G-Nv; Vtmp) {//找到所有节点中的最大的时间 MaxTime MaxTime G-heads[Vtmp].Earliest ? MaxTime : G-heads[Vtmp].Earliest; } for (Vertex Vtmp 1; Vtmp G-Nv; Vtmp) {//初始化所有节点的Latest时间为MaxTime G-heads[Vtmp].Latest MaxTime; } while (s.empty() ! 1) {//按照栈的顺序进行反序修改Latest V s.top(); s.pop();//反序弹出V for (tmp G-heads[V].FirstEdge; tmp ! NULL; tmp tmp-Next) { W tmp-V; if (G-heads[V].Latest G-heads[W].Latest - tmp-Weight) { G-heads[V].Latest G-heads[W].Latest - tmp-Weight;//更新V点的Latest } } } for (Vertex Vtmp 1; Vtmp G-Nv; Vtmp) {//对所有边对象更新Delay tmp G-heads[Vtmp].FirstEdge; while (tmp ! NULL) { W tmp-V; tmp-Delay G-heads[W].Latest - (G-heads[Vtmp].Earliest tmp-Weight);//计算边v,w的delay tmp tmp-Next; } } return 1; } int FindMaxTime(Graph G) { int MaxTime 0; for (Vertex Vtmp 1; Vtmp G-Nv; Vtmp) { MaxTime MaxTime G-heads[Vtmp].Earliest ? MaxTime : G-heads[Vtmp].Earliest; } return MaxTime; } void DispRes(int res, Graph G) { if (res 0) { cout 0; } else if (res 1) { int MaxTime FindMaxTime(G); multimapVertex, PtrToLNode path; PtrToLNode tmp;//边对象 for (Vertex V 1; V G-Nv; V) { tmp G-heads[V].FirstEdge; while (tmp ! NULL) { if (tmp-Delay 0) {//判断是否是关键路径 path.insert(make_pair(V, tmp)); } tmp tmp-Next; } } cout MaxTime endl; for (auto pt path.begin(); pt ! path.end(); pt) { cout pt-first - pt-second-V endl; } } } int main() { int N, M; cin N M; Graph G BuildGraph(N, M); int res; resTopSorting(G); DispRes(res, G); return 0; }测试结果总结1.各种结构写得比较清晰命名方面有了新的体会比如为什么头节点那里要命名为VNode其实和GraphNode差不多同理边那里其实我不该写成LNode这个是链表的命名写成ENode会更好也体会到了AdjList这个邻接表的真正含义虽然只是命名但是其实很讲究2.使用了STL里面的队列和栈在实验书中提到了用队列和栈来实现顺序和逆序虽然很朴素但是这里使用栈就显得十分的巧妙。用队列顺序层序的计算Earliest自然不必说而用栈来倒序计算Latest是一个很不错的思路3.关键路径的 拓扑排序计算过程其实并不复杂我做完了这个问题有2个体会一个就是任何的算法和解决过程出了关注过程本身是如何解决的先干什么再干什么还需要注意这个算法在什么情况下会失效。比如最短路径里面的“负值圈”问题而拓扑排序则是不连通的问题我在这里是通过统计队列弹出的点数来判断十分失效的。另外就是在执行算法的时候数据结构和算法是统一的。在图论里面有图结构有点结构有边结构我在这一题里面特意的没有另外使用额外的数组将所有的信息全部存在了图中存在了边结构和点结构中。这个时候理清楚每一个结构具有哪些特性就很重要了。比如上面的EarliestLatest和InDegree作为每个节点的属性应该被添加到图的邻接表里面每个顶点的属性中因此添加到VNode这个结构中是合理的。而每个过程也就是每一条边除了自身的权重外它还有相应的机动时间这个时候把Delay作为边的属性是更合理的。4.最后就是在输出结果的时候把所有的关键路径收入一个结构中进行输出考虑到同一个顶点往外发出可能有多条关键路径因此我选择了multimapkey,typename这种数据结构具体来说就是multimapVertex,PtrToLNode这种数据结构因为map这种结构本身会根据key的值来进行排序十分方便。但是关于第二个部分是如何排序的为什么又会符合题目要求的输出我觉得我自己还要看一下相关的资料这样下次可以自己写一个map结构出来。multimap插入顺序说明key按升序排列相同的key是按插入先后进行排列#includeiostream #includemap #includeutility using namespace std; int main() { multimapint, char res; res.insert(make_pair(1, a)); res.insert(make_pair(2, g)); res.insert(make_pair(1, c)); res.insert(make_pair(1, b)); for (auto p res.begin(); p ! res.end(); p) { cout p-second endl; } return 0; }