训练计划
计算机软件能力认证考试系统
这道题70分还是很好拿的。后面30分需要用到 反向拓扑排序 ，相对而言就麻烦点，需要逆序遍历。不着急，我们慢慢来。首先给出70分的代码。
本题可以学到：反向拓扑排序
70分题解：
#include <iostream>
#include <vector>
using namespace std;
const int N=366;
//如果只考虑70%，都不能满足，被依赖者越早发生越好。
//剩下的30%，应该是无依赖，和依赖也能完成，被依赖者可以适当延后
//我们可以先按照越早发生的情况把相应的算出来，并记录好这条链。然后从最晚发生的开始，向上增加天数。
//但是问题在于，这只能改这一条上的数据。如果有链和其相交，交点位置改变，会影响支链的情况。
//好吧，那就先只弄70分的吧
int n,m; //距离大赛开幕的天数 训练科目的数量
vector<int>depend(N); //依赖情况
vector<int>cost(N); //消耗天数
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++) cin>>depend[i];
for(int i=1;i<=m;i++) cin>>cost[i];
for(int i=1;i<=m;i++)
{
if(depend[i]==0) cout<<1<<" ";
else
{
int t=depend[i];
int sum=0;
while(t!=0)
{
sum+=cost[t];
t=depend[t];
}
cout<<1+sum<<" ";
}
}
return 0;
}计算最晚开始时间（latest 数组）的逻辑是基于课程的依赖关系，通过反向遍历所有课程来实现的。这种方法通常称为“反向拓扑排序”或“逆后序遍历”，因为它从没有任何依赖（即出度为0）的课程开始，然后逐步向前追溯到有依赖关系的课程。
-
初始化
-
对于所有课程，最晚开始时间（
latest数组）的初始值可以设置为一个足够大的数（比如INT_MAX），但在这个代码中，由于已经知道总时间限制为n天，并且每个课程都需要一定的时间来完成，所以更合理的初始化方式是针对没有依赖的课程（即入度为0的课程），将其最晚开始时间设置为n - cost[i] + 1，这里cost[i]是课程i所需的训练天数。
-
-
反向遍历
从
m（最后一个课程的编号）开始，递减遍历到1（第一个课程的编号）。对于每个课程
i-
如果课程
i没有依赖（即mp[i].size() == 0），则直接根据总时间限制和该课程的训练天数来设置其最晚开始时间：latest[i] = n - cost[i] + 1。这是因为没有任何课程依赖于课程i，所以课程i可以在不迟于n - cost[i] + 1天开始，以确保在n天内完成。 -
如果课程
i有依赖（即mp[i].size() > 0），则需要找到所有依赖于课程i的课程（即mp[i]中的课程）的最晚开始时间中的最小值，然后从这个最小值中减去课程i的训练天数来得到课程i的最晚开始时间。这是因为课程i必须在其所有依赖课程之后开始，以确保在它们完成之后才能开始课程i。我在代码中举了例子，大家可以看看。
-
-
计算过程
-
在计算过程中，由于是从后向前遍历，所以当一个课程的最晚开始时间被计算出来时，它的所有依赖课程的最晚开始时间都已经被计算过了。这使得我们能够正确地找到依赖课程中的最晚开始时间的最小值。
AC:
-
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int n,m;
map<int,vector<int>>mp; // <科目i,<依赖于i的科目集合>>
bool f=false; //判断是否能在规定时间内训练完
int main()
{
cin >>n>>m;
vector<int> depend(m + 1); //科目i所依赖的科目depend[i]
vector<int> cost(m + 1); //科目i所需的训练天数
vector<int> earlist(m + 1); //科目i最早开始时间
vector<int> latest(m + 1); //科目i最晚开始时间
for (int i = 1; i <= m; i++)
{
cin >> depend[i];
mp[depend[i]].push_back(i);
}
for (int i = 1; i <= m; i++) cin >> cost[i];
for (int i = 1; i <= m; i++)
{
if (depend[i] == 0)
earlist[i] = 1;
else
{
int k = depend[i];
earlist[i] = earlist[k] + cost[k];
if (earlist[i] + cost[i] > n)
f = true; //表示不能在规定时间内做完
}
cout << earlist[i] << " ";
}
if (f) //不能做完，那就到此为止
return 0;
//能在规定时间内做完，继续输出最晚开始时间
cout<<endl;
for (int i = m; i >= 1; i--)
{
if (mp[i].size() == 0)
latest[i] = n - cost[i] + 1;
else
{
int min_num = latest[mp[i][0]];
//所有依赖课程的最晚开始时间中的最小值，也就是最先完成的依赖课程
for (int j = 0; j < mp[i].size(); j++) {
if (latest[mp[i][j]] < min_num)
min_num = latest[mp[i][j]];
}
latest[i] = min_num - cost[i];
/*当前课程的最晚开始时间不是由他决定的，而是由他的依赖课程决定的。
后续依赖课程都满足贴屁股完成，在此前提下，越早开始的，其最晚开始时间越小。
我们就是要满足这个最小时间，才能确定当前课程i的最晚开始时间。
比如有2、3都依赖1。现在我们想确定1的最晚开始时间。
已知2的最晚开始时间是5，到10结束；3的最晚开始时间是7，到10结束；cost[1]=1。
按照上述方法，我们应该选择5作为min_num，然后计算latest[1]=5-cost[1]=4，作为1的最晚开始时间。
如果我们选择7，latest[1]=7-cost[1]=6。
然后我们发现，2的最晚开始时间是5,1的最晚开始时间是6，但是2又依赖于1，1本应该比2先开始。
所以出现矛盾。*/
}
}
for (int i = 1; i <= m; i++) cout << latest[i] << " ";
return 0;
}参考代码：【CCF CSP】202212-2 训练计划-CSDN博客
