题目：训练计划

此题目样例有坑：样例中没有正确输出过一个最晚开始时间

所以在最开始处理问题的时候，直接将最晚开始时间处理成最晚=n+1-T[i]，其中，T[i]代表项目i所占用的时间。这也是一开始一直只能得到70分的原因（就这让我还以为，计算最早开始时间出错，一直在想哪里有问题）

计算最早/最晚开始时间

根据样例二，分别计算最早/最晚开始时间

最早开始时间

最早开始时间	value	最早开始时间	value
E[1]	1	E[5]	max{1,1+T[1]+T[2]}
E[2]	max{1, 1+T[1]}	E[6]	max{1,1+T[3]}
E[3]	1	E[7]	1
E[4]	max{1, 1+T[3]}

表中，E代表最早开始时间，T代表项目需要时间。例如：E[5]，代表项目5的最早开始时间；T[5]，代表项目5所需时间。
另外，还使用到了D、L数组。D代表depend依赖；L，代表最晚开始时间

也就是说，只要遍历项目5的依赖，就可以计算出项目5的最早开始时间，而题目提供的树中父亲表示法的结构，也适合进行该操作。
由于题目中说明了最多有1个依赖，所以直接采用依赖数组D，去递推计算即可。
所以最开的想法是：采用while循环，一直遍历到D[i]==0时，去计算最早发生时间。

for(int i=1;i<=m;++i){int t=1,d=i;while(D[d]!=0){t += T[D[d]];d = D[d];//更新d，用于查找上一层依赖的项目}//记录项目i的最早开始时间E[i]=t;
}

参考最优化的想法，可以知道：其实，E[5]=max{1,E[2]+T[2]}，并且由于，题目中说明了：D[i]<i，即是项目i的前置依赖项目D[i]，一定小于i，所以，可以从前往后（i从1到m），依次计算出项目i的最早开始时间

//计算最先开始时间
for(int i=1;i<=m;++i){if(D[i]!=0){E[i]=E[D[i]]+T[D[i]];}else{E[i]=1;}}

发散

倘若对于项目5而言，它有两条出边（2个依赖）

那么，E[5]=max{1, 1+T[1]+T[2] ,1+T[3]+T[4]}。

最晚开始时间

最晚开始时间	value	最晚开始时间	value
L[1]	min{n, n+1-T[5]-T[2]-T[1]}	L[5]	min{n, n+1-T[5]}
L[2]	min{n, n+1-T[5]-T[2]}	L[6]	min{n, n+1-T[6]}
L[3]	min{n, n+1-T[3], n+1-T[6]-T[3], n+1-T[4]-T[3]}	L[7]	min{n , n+1-T[7]}
L[4]	min{n, n+1-T[4]}

根据AOE网的计算顺序，可以知道，采用从后往前算（i从7到1）。其中比较难处理的是项目3
首先，同样采用将L带入表达式中，那么有：

L[3] = min{n, n+1-T[3], n+1-T[6]-T[3], n+1-T[4]-T[3]}
=min{n, n+1-T[3], L[6]-T[3], L[4]-T[3]}

项目3有2条进边，但是可以知道其中，L[6]-T[3]可以先于L[4]-T[3]被计算出来（因为可以通过D[6]=3，找到项目6的依赖项目3，从而先计算出L[6]-T[3]，而当遍历i=4时，又可以计算出L[4]-T[3]，…，从而一直遍历到i=3）
故有如下代码：

    //初始条件：L[1,...,7]={n,...,n}bool flag=true;//是否可以完成训练计划//计算最后开始时间for(int i=m;i>=1;--i){L[i]=min(L[i],n+1-T[i]);if(D[i]!=0){L[D[i]]=min(L[D[i]],L[i]-T[D[i]]);}if(L[i]<=0) flag=false;}

代码与上机

代码

#include<bits/stdc++.h>
using namespace std;const int maxn=105;
int D[maxn],T[maxn];//D[i]==j:i的依赖是j，T[i]:项目i所需时间
int E[maxn],L[maxn];//E:最早开始时间， L:最晚开始时间
int main(){//接收题目输入int n,m;cin>>n>>m;for(int i=1;i<=m;++i){cin>>D[i];}for(int i=1;i<=m;++i){cin>>T[i];}//计算最先开始时间for(int i=1;i<=m;++i){if(D[i]!=0){E[i]=E[D[i]]+T[D[i]];}else{E[i]=1;}L[i]=n;//初始化L数组}bool flag=true;//计算最后开始时间for(int i=m;i>=1;--i){L[i]=min(L[i],n+1-T[i]);if(D[i]!=0){L[D[i]]=min(L[D[i]],L[i]-T[D[i]]);}if(L[i]<=0) flag=false;}for(int i=1;i<=m;++i){cout<<E[i]<<" ";}if(flag){cout<<endl;for(int i=1;i<=m;++i){cout<<L[i]<<" ";}}//system("pause");return 0;
}

上机结果