PTA 天梯赛 7-11：关键活动 ← AOE网
【题目来源】
https://pintia.cn/problem-sets/15/exam/problems/type/7?problemSetProblemId=719
https://pintia.cn/problem-sets/15/exam/problems/type/7
【题目描述】
假定一个工程项目由一组子任务构成，子任务之间有的可以并行执行，有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。
比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程，各门课程可以看成是子任务。有些课程可以同时开设，比如英语和C程序设计，它们没有必须先修哪门的约束；有些课程则不可以同时开设，因为它们有先后的依赖关系，比如C程序设计和数据结构两门课，必须先学习前者。
但是需要注意的是，对一组子任务，并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B，子任务B依赖于子任务C，子任务C又依赖于子任务A”，那么这三个任务哪个都不能先执行，这就是一个不可行的方案。
任务调度问题中，如果还给出了完成每个子任务需要的时间，则我们可以算出完成整个工程需要的最短时间。在这些子任务中，有些任务即使推迟几天完成，也不会影响全局的工期；但是有些任务必须准时完成，否则整个项目的工期就要因此延误，这种任务就叫“关键活动”。
请编写程序判定一个给定的工程项目的任务调度是否可行；如果该调度方案可行，则计算完成整个工程项目需要的最短时间，并输出所有的关键活动。
【输入格式】
输入第 1 行给出两个正整数 N(≤100)和 M，其中 N 是任务交接点的数量。其中，任务交接点，即衔接相互依赖的两个子任务的节点，例如：若任务 2 要在任务 1 完成后才开始，则两任务之间必有一个交接点。
随后 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
【算法分析】
● 在 AOE 网中，存在关键路径的前提是“无环”，可利用“拓扑排序”进行判定。
● 在 AOE 网中，满足 la(a)-ea(a)=0 的活动 a 是关键活动。其中，ea(a)表示活动a的最早开始时间，la(a)表示活动a的最迟开始时间。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int maxn=105;
const int inf=0x3f3f3f3f;
int g[maxn][maxn];
int ee[maxn], le[maxn]; //early event, late event
int ind[maxn], cud[maxn]; //inDegree, outDegree
int path[maxn];
queue<int> q;void outputPath(int n, int tot, int mxt) { //maxTimeif(tot!=n) cout<<0; //has circuit in graphelse {cout<<mxt<<endl;for(int i=1; i<=n; i++)for(int j=n; j>=1; j--)if(g[i][j]<inf && g[i][j]==le[j]-ee[i])cout<<i<<"->"<<j<<endl;}
}void criticalPath(int n) {for(int i=1; i<=n; i++) {if(ind[i]==0) {q.push(i);ind[i]=-1;}}int cnt=0;while(!q.empty()) { //calcute eeint t=q.front();q.pop();cnt++;for(int i=1; i<=n; i++) {if(g[t][i]<inf) {ee[i]=max(ee[i],ee[t]+g[t][i]);ind[i]--;}if(ind[i]==0) {q.push(i);ind[i]=-1;}}}int mxt=0, maxIndex=0;for(int i=1; i<=n; i++) {if(ee[i]>mxt) {mxt=ee[i];maxIndex=i;}}le[maxIndex]=mxt;for(int i=1; i<=n; i++) {if(cud[i]==0) {q.push(i);cud[i]=-1;}}while(!q.empty()) { //calcute leint t=q.front();q.pop();for(int i=1; i<=n; i++) {if(g[i][t]<inf) {cud[i]--;le[i]=min(le[i],le[t]-g[i][t]);}if(cud[i]==0) {q.push(i);cud[i]=-1;}}}outputPath(n,cnt,mxt);
}int main() {memset(le,inf,sizeof le);int n,m;cin>>n>>m;for(int i=1; i<=n; i++) {for(int j=1; j<=n; j++)g[i][j]=g[j][i]=inf;}int a,b,c;while(m--) {cin>>a>>b>>c;g[a][b]=c;ind[b]++; //inDegreecud[a]++; //outDegree}criticalPath(n);return 0;
}/*
in:
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 2out:
17
1->2
2->4
4->6
6->7
*/
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/127530053
https://pintia.cn/problem-sets/15/exam/problems/type/7?problemSetProblemId=719
https://pintia.cn/problem-sets/15/exam/problems/type/6
https://pintia.cn/problem-sets/15/exam/problems/type/7
https://www.acwing.com/solution/leetcode/content/62822/
https://blog.csdn.net/Atl212/article/details/119009752
https://www.codeleading.com/article/60953073553/