这题本来就是个拓扑排序，搞了半天竟然搞不出来，想了半天。。
一开始的想法是：搞拓扑排序，一轮一轮的扫描，每一轮出一个最大时间，把最大时间相加就好了，后来发现全WA，为什么呢？因为同一轮里出来的任务其实有可能是不互相依赖的。比如任务1时间需要10；任务2时间需要5；任务3需要在任务1之后，任务4需要在任务2之后。如果一轮一轮的扫描，那么必须10秒之后同时开始做任务3/4。而实际情况则应该是任务2，5个时间作完之后就可以做任务4了。根据失误我又想着反向建图，用DFS递归解决，对每个结点（及其之前节点）找其最大的所用时间，写出来AC了（对于本题，杂务 k(k>1)的准备工作只可能在杂务 1 至 k-1 中，如果没有这个要求，反向建图就很好）。但是其实我想多了。直接一开始的拓扑排序，顺着推就可以了。
DFS版：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | #include<iostream> #include<vector> #include<algorithm> using namespace std; int n,times[10005],inDegree[10005],f[10005]; vector<int> edges[10005]; vector<int> curTasks; int dfs(int node){ if(f[node]!=0)return f[node]; if(edges[node].size()==0)return f[node]=times[node]; int maxT=0; for(int i=0;i<edges[node].size();i++){ maxT=max(maxT,dfs(edges[node][i])); } return f[node]=maxT+times[node]; } int main(){ ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++){ int v; cin>>v>>times[i]; while(1){ cin>>v; if(v==0)break; edges[i].push_back(v); inDegree[v]++; } } int maxTime=0; for(int i=1;i<=n;i++){ if(inDegree[i]==0)maxTime=max(maxTime,dfs(i)); } cout<<maxTime; } |
正常版：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | #include<iostream> #include<vector> #include<algorithm> using namespace std; int n,times[10005],inDegree[10005],allTimes[10005]; vector<int> edges[10005]; int sumTime=0; int main(){ ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++){ int v; cin>>v>>times[i]; while(1){ cin>>v; if(v==0)break; edges[v].push_back(i); inDegree[i]++; } } int maxT=0; for(int i=1;i<=n;i++)if(inDegree[i]==0){ allTimes[i]+=times[i]; for(int j=0;j<edges[i].size();j++){ allTimes[edges[i][j]]=max(allTimes[edges[i][j]],allTimes[i]); inDegree[edges[i][j]]--; } inDegree[i]--; maxT=max(maxT,allTimes[i]); } cout<<maxT; } |