洛谷 P1113 杂务

这题本来就是个拓扑排序,搞了半天竟然搞不出来,想了半天。。
一开始的想法是:搞拓扑排序,一轮一轮的扫描,每一轮出一个最大时间,把最大时间相加就好了,后来发现全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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注