技术分享
关键路径
00 min
2024-7-23
2024-7-30
type
status
date
slug
summary
tags
category
icon
password

题目:关键路径

 
假定一个工程由若干子任务构成,使用一个包含n个顶点、e条边的 AOE 网表示该工程,顶点编号为1至n,有向边表示该工程的每个子任务,边的权值表示完成该子任务所需的时间,假定网中只含一个源点(入度为0的顶点,称为源点)和一个汇点(出度为0的顶点,称为汇点)。
关键路径AOE 网中,从源点到汇点的所有路径中,其中具有最大路径长度(长度指的是路径上边的权重和)的路径称为关键路径。
关键活动:关键路径上的边。
由于 AOE 网中的某些活动能够同时进行,故完成整个工程所必须花费的时间应该为始点到终点的最大路径长度。关键路径长度是整个工程所需的最短工期
请编写程序求出该工程从源点到汇点的关键路径长度。

输入格式:

每个测试点包含多组测试数据。每组数据第一行为2个整数n和e,均不超过200,分别表示 AOE 网的顶点数和边数。接下来e行表示每条边的信息,每行为3个正整数a、b、c,其中a和b表示该边的端点编号,c表示权值。各边并不一定按端点编号顺序排列,且各顶点并不一定按拓扑序排列。

输出格式:

对每组数据,若工程不可行(AOE网中存在环),输出“unworkable project”;若工程可行,则输出第一行为完成工程所需的关键路径长度,并从第2行开始输出关键活动,每个关键活动占一行,格式为i->j,其中i和j表示关键活动所在边的端点编号。各关键活动输出顺序为:按i的递增顺序输出,若多个关键活动的i值相同,则按j的递增顺序输出。
 

输入样例:

在这里给出一组输入。例如:

输出样例:

在这里给出相应的输出。例如:
 

思路与题解

 
  • 推演图
notion image
• etv从左向右推导
notion image
• ltv从右向左推导
notion image
 
• ete: 活动最早开工时间需要和etv事件最早发生时间结合
notion image
• lte: 活动最晚开工时间需要和ltv事件最晚发生时间结合(都是倒序获得)
notion image
 
 
 

附录

 
上一篇
最长的美好子字符串
下一篇
最长有效括号