OneCoder Avatar
OneCodercoderli.com · 1022 篇博文
⌘ CSP-S

CSP-S 提高级题解

🎨 视觉封面

【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P1113 [USACO02FEB] 杂务

📅 2026-10-02·✍️ OneCoder·计算中...·⏱️ 15 分钟

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

luogu-P1113 [USACO02FEB] 杂务

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

题目描述

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

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

输入格式

第1行:一个整数,必须完成的杂务的数目();

第至行: 共有行,每行有一些用个空格隔开的整数,分别表示:

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

* 完成工作所需要的时间;

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

输出格式

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

输入输出样例

样例输入 #1

Code8 行
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

Code1 行
23

说明/提示

数据范围与约定:

  • 对于 的数据,保证 ,。
  • 每项杂务的准备工作总数不超过 个,且杂务 的准备工作编号必定属于 。

题目深度剖析

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

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

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

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

定义状态:

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

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

  • 若杂务 没有准备工作(前置集合 ),则该任务在时刻 即可立即开工,其最早完成时刻等于其自身的耗时:

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

  • 设杂务 的直接准备工作集合为 。
  • 由于所有准备工作必须全部完成方可开始任务 ,任务 的最早开工时刻为:
  • 加上任务 自身的持续时间 ,即可得到完成任务 的最早时刻:

全局目标:

  • 题目的目标是“所有杂务都被完成的最短时间”。由于各任务的分支路径独立推进,最终完成所有杂务的时间,必定等于所有杂务完成时刻的最大值:

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

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

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

“杂务 的准备工作只可能在杂务 至 中。”

这意味着:

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

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

  • 时间复杂度:
    • 共有 个任务,每个任务的前置准备工作最多 个,总依赖边数 。
    • 算法只需单层循环从 到 遍历每个任务,内部通过一个小型 while 循环读入前置编号并求最大值。
    • 总时间复杂度严格为 。对于 ,,执行操作仅在毫秒级(约 ),轻松通过 的时间限制。
  • 空间复杂度:
    • 仅需一个大小为 的全局静态一维数组 f,内存占用不到 ,远低于 的空间上限。

样例手推演算

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

  • 项杂务
杂务编号 自身耗时 前置准备工作 最晚前置完工时刻 本任务最早完工时刻 状态推导说明
1 5 无(0 结束) 起始基准任务,时刻 0 开工
2 2 1 依赖任务 1,时刻 5 开工
3 3 2 依赖任务 2,时刻 7 开工
4 6 1 依赖任务 1,时刻 5 开工
5 1 2, 4 依赖 2 和 4,必须等待 4 完工方可开工
6 8 2, 4 依赖 2 和 4,耗时较长
7 4 3, 5, 6 依赖 3、5、6,必须等待 6 完工方可开工

全图所有任务最早完成时刻的最大值为: 样例手推结果与洛谷样例输出 23 完全一致。


易错点与边界防坑指南

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

C++ 完整参考实现

C++53 行
/**
 * 题目: 【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;
}
看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!