题目链接
关键路径问题，也是拓扑排序的变形，只用额外增加一个数组记录每个任务的最晚完成时间即可。
对于每个节点(activity)，我们需要记录他们的入度和最晚完成时间，入度为0的结点可执行，最晚时间的更新按最大来
具体解释在代码中：
#include<iostream>#include<vector>#include<queue>#define MAX 10000000using namespace std;int main(){int n, m, s, e, l;cin >> n >> m;vector<vector<int>> activitylink(n, vector<int>(n, -1));//记录是否连通vector<int> indegree(n);//记录入度vector<int> latest(n);//记录最晚完成时间vector<bool> isused(n, false);//记录节点是否被考虑queue<int> Q;for (int i = 0; i < m; i++)//数据读入{cin >> s >> e >> l;activitylink[s][e] = l;indegree[e]++;}int act = -1;for(int i = 0;i<n;i++)//初始时将所有入度为0的点入队if (indegree[i] == 0){Q.push(i);}if (Q.empty())//如果队列空，代表没有入度为0的节点，即图是个环{cout << "Impossible" << endl;return 0;}else{while (!Q.empty()){act = Q.front();//取出一个节点Q.pop();isused[act] = true;for (int i = 0; i < n; i++){if (activitylink[act][i] != -1 && !isused[i])//对与该节点连通的节点{indegree[i]--;//入度减1if (indegree[i] == 0)//减后入度为0即入队Q.push(i);//与当前节点连通的节点，计算经过当前节点所需时间与原时间，取大者if (latest[act] + activitylink[act][i] > latest[i])latest[i] = latest[act] + activitylink[act][i];}}}}for(int i = 0;i<n;i++)if (!isused[i])//有环{cout << "Impossible" << endl;return 0;}int completetime = 0;for (int i = 0; i < n; i++)//最大值为最少需要的时间{if (latest[i] > completetime)completetime = latest[i];}cout << completetime << endl;return 0;}
如果觉得《08-图8 How Long Does It Take (25分)》对你有帮助，请点赞、收藏，并留下你的观点哦！
