主题说明：假设一个项目由一系列子任务组成。 一些子任务可以并行执行，而其他子任务必须在完成后才能执行。 任务进度表包括一组子任务和一组每个子任务依赖的子任务。
例如，完成专业所有课程的学习和毕业设计可以视为本科生需要完成的一项工程，而每门课程都可以视为子任务。 虽然也有可以同时开设英语和C编程等课程的课程，但是没有必须先修哪一门的制约。 有些课程存在前后依存关系，如c编程和数据结构两门课程，所以不能同时开设。 首先，你需要学习前者。
但是，请注意，对于一组子任务，任何任务时间表都不一定是可执行的方案。 例如，如果计划中存在“子任务a依赖于子任务b，子任务b依赖于子任务c，子任务c依赖于子任务a”，则这三个任务都不能先执行。 这是不可能的计划。
在任务调度问题中，如果显示了完成各个子任务所需的时间，则可以计算出完成整个项目所需的最短时间。 其中一些子任务即使延迟几天完成，也不会影响整体工期。 但是，有些任务必须按时完成。 否则，整个项目工期必须因此延误。 这样的任务被称为“重要活动”。
请制定判断指定工程项目的任务日程是否可行的程序。如果日程方案可行，计算完成整个工程项目所需的最短时间，并输出所有重要活动。
在格式：中输入第一行时，将给出两个正整数N(100 )和m。 其中，n是任务传递点，也就是连接两个子任务(相互依赖)的节点。 例如，如果要在任务1完成后启动任务2，则两个任务之间必须有一个传递点。 交接点按1~N号。 m是子任务的数量，按1~M的顺序编号。 在随后的m行中，每行给出三个正整数。 分别是与任务开始和完成相关的传递点编号和任务完成所需的时间，整数之间用空格分隔。
如果不能进行输出格式：任务调度，则输出0； 否则，第一行输出整个工程项目完成所需的时间，第二行开始输出所有重要活动，每个重要活动占一行，以形式“V-W”输出。 其中，v和w是与该任务的开始和完成有关的交接点编号。 关键活动的输出顺序规则以任务开始交接点编号小的优先，如果起点编号相同，则输入时和任务顺序相反。
输入示例：78124133245343451466575672输入示例：171-22-44-66-7http://www.Sina.com/http://www.Sina.com /
题解：
1.有关键路径的前提是【无环】，所以也就用到了【拓扑排序的思想】。
2.求关键路径的重点在于求每个项目的【最早开始时间 es】和【最晚结束时间 le】。测试点结果显示耗时内存0sample 4选择4条简单路径正确
3 ms384 KB1单起点和单目标，两条关键路径的答案是正确的
2 ms304 KB2多起点和多目标答案正确
2 ms384 KB3不可行的答案是正确的
3 ms368 KB4最大n，简单电路无法正确操作
5 ms424 KB5最大n，随机，可行答案正确
4 ms 412 kb # include iostream # include cstring # includequeueusingnamespacestd； int g[102][102]； //图int es[102]，le[102]； //earliest start，latest endqueueint q； const int inf=0x3f3f3f3f； int path[102]，plen=0； //关键路径int indegree[102]，outdegree[102]； //入、出、voidoutputpath(intn，int cnt，int maxTime )//关键路径if ) CNT！=n () /有环cout 0； } else { cout maxTime endl； for(intI=1； i=n； I ) for(intj=n； j=1； j-- ) if (g [ I ] [ j ] infg [ I ] [ j ]==le [ j ]-es [ I ] ) cout i '-' j endl； }关键路径输入路径(输入) /关键路径输入u计算； int cnt=0； //为了判断有无循环for而进行计数
(int i = 1; i <= n; i++) if (indegree[i] == 0){ q.push(i); indegree[i] = -1; // 标记为已入队 } while (!q.empty()){ // 计算 es --------------------------- u = q.front(); q.pop(); cnt++; // 计数 for (int i = 1; i <= n; i++){ if (g[u][i] < inf){ es[i] = max(es[i], es[u]+g[u][i]); indegree[i]--; } if (indegree[i] == 0){ // 再次判断，入度为零的点入队 q.push(i); indegree[i] = -1; } } // for } // while int maxTime = 0, maxIndex = 0; for (int i = 1; i <= n; i++) // 找最大工程时间，及末尾工程 if (es[i] > maxTime){ maxTime = es[i]; maxIndex = i; } le[maxIndex] = maxTime; for (int i = 1; i <= n; i++) // 出度为零的点入队 if (outdegree[i] == 0){ q.push(i); outdegree[i] = -1; } while (!q.empty()){ // 计算 le ----------------------------- u = q.front(); q.pop(); for (int i = 1; i <= n; i++){ if (g[i][u] < inf){ outdegree[i]--; le[i] = min(le[i], le[u]-g[i][u]); } if (outdegree[i] == 0){ // 再次判断，出度为零的点入队 q.push(i); outdegree[i] = -1; } } // for } // while outputPath(n, cnt, maxTime);}int main() { int n, m; int maxTime = 0; int a, b, cost; memset(es, 0, sizeof(es)); memset(indegree, 0, sizeof(indegree)); memset(outdegree, 0, sizeof(outdegree)); cin >> n >> m; for (int i = 1; i <= n; i++) // 初始化 for (int j = 1; j <= i; j++) g[i][j] = g[j][i] = inf; for (int i = 1; i <= n; i++) // 初始化 le[i] = inf; for (int i = 0; i < m; i++){ // 构图 cin >> a >> b >> cost; g[a][b] = cost; indegree[b]++; outdegree[a]++; } criticalPath(n); return 0;}