做网站初始配置,能源网站建设公司,最好最全的搜索引擎,成都网站搜索引擎优化参考链接#xff1a;https://blog.csdn.net/tianwei0822/article/details/88642441
一个项目由若干个任务组成#xff0c;任务之间有先后依赖顺序。项目经理需要设置一系列里程碑#xff0c;在每个里程碑节点处检查任务的完成情况#xff0c;并启动后续的任务。现给定一个…参考链接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));cinnm;int t1,t2,t;for (int i0;im;i){cint1t2t;Map[t1][t2]t;times[t2];}int judgeTop();if (judge0){printf(Impossible\n);return 0;}printf(%d,judge);return 0;
}int Top()
{int count0;stackints;for (int i0;in;i){if (times[i]0){s.push(i);}}int top;while (!s.empty()){tops.top();s.pop();count;for (int j0;jn;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 max0;for (int i0;in;i){if (t[i]t[max]){maxi;}}return t[max];
}
