泰安网站建设电话,个人网站域名取名,佛山网站推广 优帮云,discuz修改网站关键词假定一个工程项目由一组子任务构成#xff0c;子任务之间有的可以并行执行#xff0c;有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。 比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成… 假定一个工程项目由一组子任务构成子任务之间有的可以并行执行有的必须在完成了其它一些子任务后才能执行。“任务调度”包括一组子任务、以及每个子任务可以执行所依赖的子任务集。 比如完成一个专业的所有课程学习和毕业设计可以看成一个本科生要完成的一项工程各门课程可以看成是子任务。有些课程可以同时开设比如英语和C程序设计它们没有必须先修哪门的约束有些课程则不可以同时开设因为它们有先后的依赖关系比如C程序设计和数据结构两门课必须先学习前者。 但是需要注意的是对一组子任务并不是任意的任务调度都是一个可行的方案。比如方案中存在“子任务A依赖于子任务B子任务B依赖于子任务C子任务C又依赖于子任务A”那么这三个任务哪个都不能先执行这就是一个不可行的方案。 任务调度问题中如果还给出了完成每个子任务需要的时间则我们可以算出完成整个工程需要的最短时间。在这些子任务中有些任务即使推迟几天完成也不会影响全局的工期但是有些任务必须准时完成否则整个项目的工期就要因此延误这种任务就叫“关键活动”。 请编写程序判定一个给定的工程项目的任务调度是否可行如果该调度方案可行则计算完成整个工程项目需要的最短时间并输出所有的关键活动。 输入格式: 输入第1行给出两个正整数N(≤)和M其中N是任务交接点即衔接相互依赖的两个子任务的节点例如若任务2要在任务1完成后才开始则两任务之间必有一个交接点的数量。交接点按1~N编号M是子任务的数量依次编号为1~M。随后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 #includecstdio
#includecstring
const int maxn 110;
const int INF 100000000;int map[maxn][maxn];
int indegree[maxn],outdegree[maxn];
int earliest[maxn],latest[maxn];void init(int n){for(int i 1; i n; i){for(int j 1; j n; j){map[i][j] -1;}indegree[i] 0;outdegree[i] 0;earliest[i] 0;latest[i] INF;}
}int max(int a,int b){return a b ? a : b;
}int min(int a,int b){return a b ? a : b;
}int early_time(int n){int queue[n];int front -1, rear -1;for(int i 1; i n; i){if(indegree[i] 0){queue[rear] i;}}int cnt 0;while(front rear){int v queue[front];cnt;for(int i 1; i n; i){if(map[v][i] 0){indegree[i]--;earliest[i] max(earliest[i],earliest[v]map[v][i]);if(indegree[i] 0){queue[rear] i;}}}}int ans 0;if(cnt ! n) ans -1;else{ans earliest[0];for(int i 1; i n; i){if(ans earliest[i]) ans earliest[i];}}return ans;
}void late_time(int n,int x){int queue[n];int front -1,rear -1;for(int i n; i 1; i--){if(outdegree[i] 0){queue[rear] i;latest[i] x;}}while(front rear){int v queue[front];for(int i n; i 1; i--){if(map[i][v] 0){outdegree[i]--;latest[i] min(latest[i],latest[v]-map[i][v]);if(outdegree[i] 0){queue[rear] i;}}}}
}int main(){int n,m;scanf(%d%d,n,m);init(n);int v,u,w;for(int i 0; i m; i){scanf(%d%d%d,u,v,w);map[u][v] w;indegree[v];outdegree[u];}int flag early_time(n);if(flag -1) printf(0\n);else{printf(%d\n,flag);late_time(n,flag);for(int i 1; i n; i){if(earliest[i] ! latest[i]) continue;for(int j n; j 1; j--){if(map[i][j] 0 earliest[j] latest[j] (latest[j] - earliest[i] map[i][j]))printf(%d-%d\n,i,j); }}}return 0;
} 转载于:https://www.cnblogs.com/wanghao-boke/p/10901852.html
