结题思路
最早时间:找每一个科目的前置科目,递归去找,前置科目返回其累计消耗时间给后置科目
最晚时间:找每一个科目的前置科目,把后置科目的时间传导给前置科目,直到第一个科目
样例
#include<iostream>
using namespace std;
int rely[102];
int next[102];
int time[102];
int early[102];
int late[102];
//寻找最早时间
int Find_early(int n){
if(rely[n] == 0){ //无依赖 直接计算
early[n] = 1; //第一天开始
return time[n]+1; // 时间延迟传导给下家
}
else{ //有依赖,递归寻找
early[n] = Find_early(rely[n]); // 把自己的早时间记下
return early[n]+time[n]; //把自己的消耗时间和上家的消耗时间一起传导下去
}
}
// 寻找最晚时间
void Find_late(int n, int days, int maxtime){ // n 表示第n个科目,days 后往前传导的时间 最晚的设置为0, maxtime最大时间
if(late[n] != 0) // 如果已经被计算过,则计算两则取大,最晚时间,late[n] 记录其最晚时间
late[n] = maxtime - max(maxtime - late[n] + 1, time[n] + days) + 1; //其累计消耗时间为maxtime - late[n] + 1
else
late[n] = maxtime - (time[n] + days) + 1; //未被计算过,直接记录消耗时间
if(rely[n] != 0){ // 如果有依赖,则把最晚时间传导给上家
Find_late(rely[n], time[n]+days, maxtime);
}
}
int main(){
//输入
int n, m; // n: days; m: num of subject
cin>>n>>m;
for(int i = 1; i<=m; i++){
cin>>rely[i];
next[i] = 0;
}
for(int i = 1; i<=m; i++)
cin>>time[i];
//最早时间计算
int maxnum = 0;
for(int i = 1; i<=m; i++){
maxnum = max(Find_early(i)-1, maxnum);
}
for(int i = 1; i<=m; i++)
cout<<early[i]<<' ';
cout<<endl;
// 判断是否超时
if(maxnum > n){
return 0;
}
//最晚时间计算
for(int i = m; i>=1; i--){
Find_late(i, 0, n);
}
for(int i = 1; i<=m; i++){
cout<<late[i]<<' ';
}
return 0;
}