P1113 [USACO02FEB] 杂务——题解

解题思路

令 dp[i] 表示工作 $i$ 完成的最早时刻。它最早能开始的时刻等于所有准备工作完成时刻的最大值，因此 dp[i]=len[i]+max(dp[pre])；没有准备工作时最大值取 0。输入顺序天然就是拓扑顺序，边读边计算即可。最终答案是所有 dp[i] 的最大值。

复杂度分析

设依赖关系总数为 $E$，时间复杂度 $O(n+E)$，空间复杂度 $O(n)$。

C++17 参考代码

#include <bits/stdc++.h>
using namespace std;
int dp[10005];
int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++){
        int id,len; cin>>id>>len;
        int best=0,x;
        while(cin>>x && x) best=max(best,dp[x]);
        dp[id]=best+len;
        ans=max(ans,dp[id]);
    }
    cout<<ans<<'\n';
    return 0;
}

#include <bits/stdc++.h> using namespace std; int dp[10005]; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; int ans=0; for(int i=1;i<=n;i++){ int id,len; cin>>id>>len; int best=0,x; while(cin>>x && x) best=max(best,dp[x]); dp[id]=best+len; ans=max(ans,dp[id]); } cout<<ans<<'\n'; return 0; }