学生什么时候知道作业(0001)

2023-12-20 21:27:39

题意

输入一个数字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.属于是半懂不懂的状态,多敲几遍,希望程设考一个这个原题?

?

文章来源:https://blog.csdn.net/L3102250566/article/details/135117062
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。