P1113 杂务

生活与工业生产中的工序流水线调度,天然蕴含着严苛的时序依赖:地基未筑不可起高楼,原料未至不可开炉灶。洛谷 P1113「[USACO02FEB] 杂务」以牧场日常作业为背景,生动抽象出工程管理与图论中的核心模型——有向无环图(DAG)的关键路径与最早完成时间计算(Critical Path Method, CPM)。本题对标 CCF GESP 七级核心考点(图论基础、拓扑排序与 DAG 动态规划)以及 CSP-S 初级图论建模。题目的核心矛盾在于:在拥有无限并发人力资源的前提下,多项存在先后依赖关系的工作交织并行,决定整个系统“木桶短板”的,并非某一孤立任务的耗时,而是从起点沿着依赖链延伸至终点的最长时序依赖链(即关键路径)。若盲目进行全局深搜或暴搜所有可能路径,极易陷入状态冗余计算的泥潭;破局的关键,在于洞悉题目隐含的结构性红利——任务依赖编号严格向后(kk 的前置只来自 1…k−11 \dots k-1),这意味着输入次序本身就是一个天然合法的拓扑序列。我们无需额外执行 Kahn 算法拓扑排序,只需借助有向无环图上的动态规划(DAG-DP),以流水线式的线性状态转移 f[i]=len[i]+max⁡j∈prev[i]f[j]f[i] = len[i] + \max_{j \in \text{prev}[i]} f[j] 在 O(n+m)O(n+m) 时间复杂度内锁定全图全局极值。题目洛谷官方难度评级为普及。

luogu-P1113 [USACO02FEB] 杂务

🔗 洛谷原题传送门:luogu-P1113 [USACO02FEB] 杂务

题目描述

John的农场在给奶牛挤奶前有很多杂务要完成,每一项杂务都需要一定的时间来完成它。比如:他们要将奶牛集合起来,将他们赶进牛棚,为奶牛清洗乳房以及一些其它工作。尽早将所有杂务完成是必要的,因为这样才有更多时间挤出更多的牛奶。当然,有些杂务必须在另一些杂务完成的情况下才能进行。比如:只有将奶牛赶进牛棚才能开始为它清洗乳房,还有在未给奶牛清洗乳房之前不能挤奶。我们把这些工作称为完成本项工作的准备工作。至少有一项杂务不要求有准备工作,这个可以最早着手完成的工作,标记为杂务11。John有需要完成的nn个杂务的清单,并且这份清单是有一定顺序的,杂务k(k>1)k(k>1)的准备工作只可能在杂务11至k−1k-1中。

写一个程序从11到nn读入每个杂务的工作说明。计算出所有杂务都被完成的最短时间。当然互相没有关系的杂务可以同时工作,并且,你可以假定John的农场有足够多的工人来同时完成任意多项任务。

输入格式

第1行:一个整数nn,必须完成的杂务的数目(3≤n≤10,0003 \le n \le 10,000);

第22至(n+1)(n+1)行: 共有nn行,每行有一些用11个空格隔开的整数,分别表示:

* 工作序号(11至nn,在输入文件中是有序的);

* 完成工作所需要的时间len(1≤len≤100)len(1 \le len \le 100);

* 一些必须完成的准备工作,总数不超过100100个,由一个数字00结束。有些杂务没有需要准备的工作只描述一个单独的00,整个输入文件中不会出现多余的空格。

输出格式

一个整数,表示完成所有杂务所需的最短时间。

输入输出样例

样例输入 #1

7
1 5 0
2 2 1 0
3 3 2 0
4 6 1 0
5 1 2 4 0
6 8 2 4 0
7 4 3 5 6 0

样例输出 #1

23

说明/提示

数据范围与约定:

  • 对于 100%100\% 的数据,保证 3≤n≤10,0003 \le n \le 10,000,1≤len≤1001 \le len \le 100。
  • 每项杂务的准备工作总数不超过 100100 个,且杂务 kk 的准备工作编号必定属于 [1,k−1][1, k-1]。

题目深度剖析

1. 问题模型的数学抽象:DAG 与关键路径(CPM)

将各项杂务视作图中的顶点,将杂务之间的“准备工作(前置依赖)”视作有向边:

  • 若杂务 jj 是杂务 ii 的准备工作,则从节点 jj 向节点 ii 连一条有向边 j→ij \to i。
  • 因为杂务 kk 的准备工作只可能在杂务 11 至 k−1k-1 中,所有有向边的起点编号均严格小于终点编号(j<ij < i)。该拓扑结构天然不存在任何环路,构成了严格的有向无环图(Directed Acyclic Graph, DAG)。
  • 题目假定农场有“足够多的工人来同时完成任意多项任务”,这意味着凡是前置依赖已全部满足的任务,都可以立刻无延迟地并发启动。
  • 因此,杂务 ii 能启动的最早时刻,受制于其所有前置杂务中最晚完成的那一项。
  • 整个工程的完工总时间,取决于图中耗时最长的一条因果依赖路径,即运筹学与项目管理中经典的关键路径(Critical Path)。

2. 状态设计与 DAG-DP 状态转移方程

定义状态:

  • 设 f[i]f[i] 表示完成第 ii 项杂务所需的最早结束时刻(时间从 00 开始计时)。

基础状态(无前置准备工作的初始任务):

  • 若杂务 ii 没有准备工作(前置集合 prev[i]=∅\text{prev}[i] = \emptyset),则该任务在时刻 00 即可立即开工,其最早完成时刻等于其自身的耗时: f[i]=len[i]f[i] = len[i]

一般状态转移(存在准备工作的任务):

  • 设杂务 ii 的直接准备工作集合为 prev[i]={j1,j2,…,jm}\text{prev}[i] = \{j_1, j_2, \dots, j_m\}。
  • 由于所有准备工作必须全部完成方可开始任务 ii,任务 ii 的最早开工时刻为: start[i]=max⁡j∈prev[i]f[j]\text{start}[i] = \max_{j \in \text{prev}[i]} f[j]
  • 加上任务 ii 自身的持续时间 len[i]len[i],即可得到完成任务 ii 的最早时刻: f[i]=len[i]+max⁡j∈prev[i]f[j]f[i] = len[i] + \max_{j \in \text{prev}[i]} f[j]

全局目标:

  • 题目的目标是“所有杂务都被完成的最短时间”。由于各任务的分支路径独立推进,最终完成所有杂务的时间,必定等于所有杂务完成时刻的最大值: ans=max⁡1≤i≤nf[i]\text{ans} = \max_{1 \le i \le n} f[i]

3. 结构特异性红利:天然拓扑序与在线线性递推

在通用的 DAG 关键路径问题中,图的节点输入顺序通常是任意的。我们需要借助 Kahn 算法(统计入度,借助队列进行广度优先搜索)或 拓扑排序 先得到节点的线性偏序关系,再按照拓扑序推进动态规划转移。

然而,本题给出了一条至关重要的约束说明:

“杂务 k(k>1)k (k>1) 的准备工作只可能在杂务 11 至 k−1k-1 中。”

这意味着:

  1. 任何任务 ii 所依赖的前置任务编号 jj,必定满足 j<ij < i。
  2. 按照输入序号 1,2,…,n1, 2, \dots, n 顺序处理时,当我们枚举到任务 ii 时,其所有前置依赖任务 j∈prev[i]j \in \text{prev}[i] 必定在此之前已被完全处理,且 f[j]f[j] 的值已经确定!
  3. 因此,1,2,…,n1, 2, \dots, n 本身就是一个天然合法、无需任何额外排序的拓扑序列!
  4. 我们完全无需显式建图(无需 std::vector<int> edge[] 存储邻接表),也不需要任何拓扑排序队列,只需在循环读入每个任务及其前置任务时,在线(Online)维护最大前置时间并即时计算 f[i]f[i]。

4. 复杂度与空间开销分析

  • 时间复杂度:
    • 共有 nn 个任务,每个任务的前置准备工作最多 100100 个,总依赖边数 m≤min⁡(100n,n(n−1)/2)m \le \min(100n, n(n-1)/2)。
    • 算法只需单层循环从 11 到 nn 遍历每个任务,内部通过一个小型 while 循环读入前置编号并求最大值。
    • 总时间复杂度严格为 O(n+m)O(n + m)。对于 n=10,000n = 10,000,m≤106m \le 10^6,执行操作仅在毫秒级(约 5 ms5 \text{ ms}),轻松通过 1.00 s1.00 \text{ s} 的时间限制。
  • 空间复杂度:
    • 仅需一个大小为 N=10,005N = 10,005 的全局静态一维数组 f,内存占用不到 40 KB40 \text{ KB},远低于 125 MB125 \text{ MB} 的空间上限。

样例手推演算

以样例数据为例进行逐步演算追踪:

  • n=7n = 7 项杂务
杂务编号 ii自身耗时 lenlen前置准备工作 prev[i]\text{prev}[i]最晚前置完工时刻 max⁡f[j]\max f[j]本任务最早完工时刻 f[i]f[i]状态推导说明
15无(0 结束)000+5=50 + 5 = \mathbf{5}起始基准任务,时刻 0 开工
221f[1]=5f[1] = 55+2=75 + 2 = \mathbf{7}依赖任务 1,时刻 5 开工
332f[2]=7f[2] = 77+3=107 + 3 = \mathbf{10}依赖任务 2,时刻 7 开工
461f[1]=5f[1] = 55+6=115 + 6 = \mathbf{11}依赖任务 1,时刻 5 开工
512, 4max⁡(f[2],f[4])=max⁡(7,11)=11\max(f[2], f[4]) = \max(7, 11) = 1111+1=1211 + 1 = \mathbf{12}依赖 2 和 4,必须等待 4 完工方可开工
682, 4max⁡(f[2],f[4])=max⁡(7,11)=11\max(f[2], f[4]) = \max(7, 11) = 1111+8=1911 + 8 = \mathbf{19}依赖 2 和 4,耗时较长
743, 5, 6max⁡(f[3],f[5],f[6])=max⁡(10,12,19)=19\max(f[3], f[5], f[6]) = \max(10, 12, 19) = 1919+4=2319 + 4 = \mathbf{23}依赖 3、5、6,必须等待 6 完工方可开工

全图所有任务最早完成时刻的最大值为:

ans=max⁡(5,7,10,11,12,19,23)=23\text{ans} = \max(5, 7, 10, 11, 12, 19, 23) = 23

样例手推结果与洛谷样例输出 23 完全一致。


易错点与边界防坑指南

  1. 【防坑 1】答案并非最后一项任务的完成时间 f[n]f[n] 初学者极易理所当然地认为“第 nn 个任务必定是最后完成的,直接输出 f[n]f[n] 即可”。然而,DAG 中的末端汇点可能有多个(例如某些耗时极长的中间任务并没有后续依赖,或者第 nn 个任务本身耗时极短且依赖较早)。因此,全局最短时间必须取全员任务的极值 max⁡1≤i≤nf[i]\max_{1 \le i \le n} f[i]。
  2. 【防坑 2】无前置依赖任务的初值处理 对于没有前置依赖的任务,其前置最晚完成时间应视为 00。在读入每个任务前,务必将局部变量 max_prev_time 初始化为 00,万万不可赋为未初始化垃圾值或负数。
  3. 【防坑 3】变长前置输入的 0 哨兵终止机制 题目输入中前置工作数量不固定,且以数字 0 作为行尾终止标志。在读取前置编号时,应当采用 while (cin >> prereq && prereq != 0) 结构,既能准确处理空前置(直接读入 0),又能安全消耗流中的所有前置数字。
  4. 【防坑 4】数组规模与空间分配规范 题目数据规模为 n≤10,000n \le 10,000。根据 GESP 与 CCF 编程规范,严禁在函数内使用 C99 变长数组(VLA,如 int f[n + 1];)。应当在全局静态存储区(BSS)声明固定常量大小的数组(如 const int MAXN = 10005; int f[MAXN];),确保运行期内存安全。

C++ 完整参考实现

/**
 * 题目: 【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P1113 [USACO02FEB] 杂务
 * 题号: P1113
 * 归属: GESP七级 / CSP-S / USACO 经典题库
 * 博客: https://www.coderli.com/gesp-7-luogu-p1113/
 * 标准: C++11 (严格遵循 CCF GESP 官方规范)
 */

#include <iostream>
#include <algorithm>

using namespace std;

// 最大杂务数量常数,题目给定 n <= 10000
const int MAXN = 10005;

// f[i] 表示完成第 i 项杂务所需的最早完工时间
// 全局数组自动零初始化
int f[MAXN];

int main() {
    int n;
    cin >> n;

    int ans = 0; // 记录全场所有任务中最大的完工时间,即总工程最短总耗时

    // 依次读入每项杂务的详细说明
    // 题目性质保证:第 k 项杂务的准备工作编号必定属于 [1, k - 1]
    // 因此输入的 1 到 n 顺序天然构成了 DAG 的合法拓扑排序,支持在线单向状态转移
    for (int i = 1; i <= n; ++i) {
        int id, len;
        cin >> id >> len;

        int max_prev_time = 0; // 记录所有前置准备工作中,最晚完工的那一项的时刻
        int prereq;

        // 读入当前杂务的所有前置准备工作,以数字 0 作为结束哨兵
        while (cin >> prereq && prereq != 0) {
            max_prev_time = max(max_prev_time, f[prereq]);
        }

        // 当前杂务的最早完工时间 = 最晚前置完工时刻 + 当前任务自身所需时长
        f[id] = max_prev_time + len;

        // 维护全局所有杂务完工时刻的最大值
        ans = max(ans, f[id]);
    }

    // 输出完成全部杂务所需的最短总时间
    cout << ans << endl;

    return 0;
}

本文由coderli.com原创,按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github:https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群: 688906745

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
最后更新于