7-4 最短工期 (25 分)

参考链接：https://blog.csdn.net/tianwei0822/article/details/88642441

一个项目由若干个任务组成，任务之间有先后依赖顺序。项目经理需要设置一系列里程碑，在每个里程碑节点处检查任务的完成情况，并启动后续的任务。现给定一个项目中各个任务之间的关系，请你计算出这个项目的最早完工时间。

输入格式：
首先第一行给出两个正整数：项目里程碑的数量 N（≤100）和任务总数 M。这里的里程碑从 0 到 N−1 编号。随后 M 行，每行给出一项任务的描述，格式为“任务起始里程碑 任务结束里程碑 工作时长”，三个数字均为非负整数，以空格分隔。

输出格式：
如果整个项目的安排是合理可行的，在一行中输出最早完工时间；否则输出"Impossible"。

输入样例 1：
9 12
0 1 6
0 2 4
0 3 5
1 4 1
2 4 1
3 5 2
5 4 0
4 6 9
4 7 7
5 7 4
6 8 2
7 8 4
输出样例 1：
18
输入样例 2：
4 5
0 1 1
0 2 2
2 1 3
1 3 4
3 2 5
输出样例 2：
Impossible

这道题和之前的一道题喊山很像，都是打标记，这道题的标记是到此点的最大距离。坑点是这道题的源点和汇点不一定是唯一的，用关键路径算法直接三个点卡掉。用拓扑排序。
和喊山不同的是，这道题打标记不管用bfs或dfs都是可以的，为什么？这是因为，对于图中的每个点（里程碑），我们要的是终态，即最大的值，没有回路（回路已经返回0输出impossible结束）就保证了这个值是惟一的，即最大值与起点无关，但喊山是有回路的，必须用bfs控制层数。AC代码：

#include <bits/stdc++.h> using namespace std; int n,m; int Map[101][101],times[101],t[101]; int Top(); int main() {memset(Map,-1,sizeof(Map));cin>>n>>m;int t1,t2,t;for (int i=0;i<m;i++){cin>>t1>>t2>>t;Map[t1][t2]=t;times[t2]++;}int judge=Top();if (judge==0){printf("Impossible\n");return 0;}printf("%d",judge);return 0; }int Top() {int count=0;stack<int>s;for (int i=0;i<n;i++){if (times[i]==0){s.push(i);}}int top;while (!s.empty()){top=s.top();s.pop();count++;for (int j=0;j<n;j++){if (Map[top][j]!=-1){t[j]=max(t[j],t[top]+Map[top][j]);times[j]--;Map[top][j]=-1;if (times[j]==0){s.push(j);}}}}if (count!=n){return 0;}int max=0;for (int i=0;i<n;i++){if (t[i]>t[max]){max=i;}}return t[max]; }

总结

以上是生活随笔为你收集整理的7-4 最短工期 (25 分)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。