[USACO02FEB] 杂务

题意

每项杂务有耗时和若干准备工作。工人数量无限，没有依赖关系的工作可同时进行。求全部杂务完成的最短时间。

思路

令 finish[u] 表示任务 u 的最早完成时刻。它必须等所有准备工作结束后才能开始，因此：

finish[u]=duration[u]+\max_{v\in pre(u)}finish[v]

没有准备工作时，最大值按 0 计算。

题目保证任务按 1..n 输入，任务 u 的准备工作编号都小于 u，所以输入顺序已经是拓扑序。读完一行就能立即算出 finish[u]，不必额外建图和拓扑排序。

样例的 DP 状态如下：

任务	准备工作最晚完成	自身耗时	`finish`
`1`	`0`	`5`	`5`
`2`	`5`	`2`	`7`
`4`	`5`	`6`	`11`
`6`	`max(7,11)=11`	`8`	`19`
`7`	`max(10,12,19)=19`	`4`	`23`

最终答案是所有 finish 的最大值 23。

Python 知识

用 while data[pos] 读取以 0 结尾、长度不固定的准备工作列表。
max(current,finish[pre]) 流式维护最晚完成时间，不必保存准备工作。
max(finish) 直接得到所有任务全部结束的时刻。
充分利用输入顺序，可以同时省去邻接表、入度数组和队列。
/home/rainboy/mycode/hugo-blog/content/program_language/python/oj_input_output_cheatsheet.md：终止标记序列的解析。
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：避免不必要的大型图结构。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24import sys


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]
    pos = 1
    finish = [0] * (n + 1)

    for _ in range(n):
        task, duration = data[pos], data[pos + 1]
        pos += 2
        earliest_start = 0
        while data[pos]:
            earliest_start = max(earliest_start, finish[data[pos]])
            pos += 1
        pos += 1
        finish[task] = earliest_start + duration

    print(max(finish))


if __name__ == "__main__":
    main()

cpp

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/**
 * P1113 杂务
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005;

int len[MAXN];     // 每个任务耗时
int finish[MAXN];  // 最早完成时间
int n, ans;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int id, dur, pre;
        scanf("%d%d", &id, &dur);
        len[id] = dur;
        int earliest = 0;
        // 读入所有前置任务
        while (scanf("%d", &pre) && pre)
            earliest = max(earliest, finish[pre]);
        finish[id] = earliest + dur;
        ans = max(ans, finish[id]);
    }
    printf("%d\n", ans);
    return 0;
}

复杂度

设准备关系总数为 e，时间复杂度 $O(n+e)$ ，只保存完成时间，空间复杂度 $O(n)$ 。

总结

依赖 DP 首先要找拓扑顺序。本题已经按拓扑序输入，识别这一点后，可以边读边转移，代码比通用拓扑模板更短。

目录

题意

思路

Python 知识

代码

复杂度

总结