学生什么时候知道作业（0001）

题意

输入一个数字n，表示学生总数

输入一个数字m，表示总组长编号

接下来输入n个数字，存到arr数组里面，表示第i个学生的组长是arr[i]

接下来输入n个数字，存到time数组里面，表示第i个学生传给自己组员信息需要多长时间

问：需要多长时间可以使得所有学生知道作业

输入

6 2

2 2 -1 2 2 2

0 0 1 0 0 0?

输出

1

代码

#include<bits/stdc++.h>

using namespace std;

void dfs(int u,vector<vector<int>> &adlist,vector<int> &time,vector<int> &res)
{
	int total=0;
	for(int v:adlist[u])
	{
		dfs(v,adlist,time,res);
		total=max(total,res[v]);
	}
	res[u]=total+time[u];
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	int n,m;
	cin>>n>>m;
	
	vector<int> arr(n);
	for(int i=0;i<n;i++)	cin>>arr[i];
	
	vector<int> time(n);
	for(int i=0;i<n;i++)	cin>>time[i];
	
	vector<vector<int>> adlist(n);
	for(int i=0;i<n;i++)
	{
		if(arr[i]!=-1)	adlist[arr[i]].push_back(i);
	}
	
	vector<int> res(n,0);
	dfs(m,adlist,time,res);
	
	int ans=0;
	for(int i=0;i<n;i++)
	{
		ans=max(ans,res[i]);
	}
	
	cout<<ans<<endl;
	
	return 0;
}

总结

1.深度优先搜索

2.vector的使用

3.引用数组要加地址符号

4.初始化vector这样操作

vector<int> res(n,0);

n表示数组长度，0表示初始化的数值

5.属于是半懂不懂的状态，多敲几遍，希望程设考一个这个原题?

?