CCF刷题计划——训练计划（反向拓扑排序）

训练计划

计算机软件能力认证考试系统

这道题70分还是很好拿的。后面30分需要用到 反向拓扑排序 ，相对而言就麻烦点，需要逆序遍历。不着急，我们慢慢来。首先给出70分的代码。

本题可以学到：反向拓扑排序

70分题解：

#include 
#include 
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）的课程开始，然后逐步向前追溯到有依赖关系的课程。

1. 初始化

   • 对于所有课程，最晚开始时间（latest 数组）的初始值可以设置为一个足够大的数（比如INT_MAX），但在这个代码中，由于已经知道总时间限制为n天，并且每个课程都需要一定的时间来完成，所以更合理的初始化方式是针对没有依赖的课程（即入度为0的课程），将其最晚开始时间设置为n - cost[i] + 1，这里cost[i]是课程i所需的训练天数。

2. 反向遍历

   从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。我在代码中举了例子，大家可以看看。

3. 计算过程

   • 在计算过程中，由于是从后向前遍历，所以当一个课程的最晚开始时间被计算出来时，它的所有依赖课程的最晚开始时间都已经被计算过了。这使得我们能够正确地找到依赖课程中的最晚开始时间的最小值。

   AC:

#include 
#include 
#include 
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<
	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博客