P1113 杂务-拓扑排序

拓扑排序

P1113 杂务

题目来源-洛谷

题意

求出完成所有任务的最短时间

思路

1. 要求完成所有任务的最短时间，即每个任务尽可能最短，所以再求完成所有任务中的最大值（需要最长时间的任务都完成了才叫全部完成）

2. 问题化解：想办法求每个人的完成的最短时间（子任务中的最长时间+完成当前任务的时间）-动态规划的思想，用数组保存子任务的完成时间，然后 time[x] = max(所有子任务的完成时间-time[i]) +当前任务时间

3. 如何求所有子任务的时间？

   dfs遍历求其子任务时间 time[x] = max(dfs(子任务)-time[i]) +当前任务时间

   最后，最终结果ans = max(每个节点的最短时间) 即 ans = max(ans,dfs(i)) ,i = [1,n]

数据约束

注意数组长度即可

参考代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5+5;
int dfs(int k);
int m,n;//n个点
vector<int> p[MAXN];//邻接表存图 
int t[MAXN],f[MAXN] ;//存每个任务的时间 和完成该任务所需的最短时间 
int ans ;//存结果 
int main(){ cin>>n;int x,l,rw;//分别表示节点，完成的时间 ,必须完成的任务 for(int i=0;i<n;i++){cin>>x;cin>>t[x];while(cin>>rw){if(rw){//非0都可以说明有必须准备的任务p[x].push_back(rw);//反向存图 }else break;}} //	查看储存的数据是否正确 
//	for(int i=1;i<=n;i++){
//		for(int j=0;j<p[i].size();j++){
//			cout<<p[i][j]<<":"<<t[p[i][j]]<<" 、"; 
//		} 
//		cout<<endl;
//	}for(int i=1;i<=n;i++){ans = max(ans,dfs(i)) ;//找所有任务的最大值 } cout<<ans;return 0;
}
int dfs(int k){if(f[k]) return f[k];//有值说明访问过 for(int i=0;i<p[k].size();i++){//if(!f[p[k][i]]) 因为做当前任务都需要求出子任务最大时间，所以判断是否访问没有意思 //当前节点的完成时间是其所有子任务的最大时间+自身完成的时间f[k] = max(f[k],dfs(p[k][i]));}f[k] += t[k];//所有子任务遍历完后再来算当前值 return f[k] ;
}