丝路科技传播：工期设计与工作量评估 完整解题档案

档案概况

题目、题干与输入输出

正式题面

源文件：official-prompt.md

规则来源

• 赛项说明页码：12-13
• 训练题主题：丝路科技传播：工期设计与工作量评估
• 所属赛道：丝路文化赛道

题目背景

科技传播展项由多个任务组成，有些任务必须等前置任务完成后才能开始。项目组需要根据依赖关系和工期设计出一份最早可执行的排程方案。

任务描述

• 读取任务名称、持续天数和前置依赖。
• 在满足依赖关系的前提下，计算每个任务的最早开始时间和结束时间。
• 输出整个项目的总工期，以及按输入顺序列出的全部任务排程。
• 若输入不构成有向无环图，则输出无效结果。

输入格式

1. 第一行输入整数 n，表示任务数量。
2. 接下来 n 行，每行输入 name duration k p1 p2 ... pk。
3. k 表示前置任务个数，p1..pk 为前置任务编号，编号范围为 1..n。

输出格式

1. 若合法，第一行输出 total_days=总工期。
2. 若合法，第二行输出 schedule=，按输入顺序给出 任务名:开始-结束，使用 | 连接。
3. 若存在环，则输出 total_days=-1 和 schedule=INVALID。

数据范围与说明

• 1 <= n <= 500。
• 1 <= duration <= 10^4。
• 依赖关系可能为空。
• 同一任务的最早开始时间等于所有前置任务结束时间的最大值。

样例输入

4
A 3 0
B 2 1 1
C 4 1 1
D 2 2 2 3

样例输出

total_days=9
schedule=A:0-3|B:3-5|C:3-7|D:7-9

样例解释

• A 无依赖，因此从第 0 天开始，第 3 天结束。
• B 和 C 都依赖 A，因此都从第 3 天开始。
• D 依赖 B、C，必须等到两者都完成后在第 7 天开始，项目总工期是 9 天。

知识点清单

• 有向图依赖建模。
• 拓扑排序。
• 最早开始时间与最长路径思想。
• 入度维护。
• 循环依赖检测。

约束拆解

源文件：parsed-constraints.md

显式约束

• 1 <= n <= 500。
• 1 <= duration <= 10^4。
• 依赖关系可能为空。
• 同一任务的最早开始时间等于所有前置任务结束时间的最大值。

建模拆解

• 先明确输入的实体和字段，再把它们翻译成 拓扑排序 + 最早开始时间 DP 需要的数据结构。
• 把输出中每一项指标都和中间变量对应起来，避免最后临时拼装。
• 先用样例手推一次，再确认边界条件是否都能走到正确分支。

易错边界

• 多个任务都无前置依赖时可以同时从第 0 天开始。
• 某个任务可能依赖多个前置任务，开始时间要取最大结束时间。
• 若存在环，不能输出部分排程冒充最终答案。

计分模型

源文件：scoring-model.md

判题方式

• 主判题方式：multi-output
• 主算法：拓扑排序 + 最早开始时间 DP

判题重点

• 重点校验多项结果之间是否来自同一份最优方案，而不是分别独立计算。
• 隐藏数据会覆盖并列最优、输出顺序和备用方案为空的情况。

公开样例建议

• 至少准备 1 组题面样例、2 组边界样例和 2 组自定义回归样例。
• 多输出题必须验证所有字段都来自同一套方案。

隐藏数据建议

• 验证所有任务都无依赖的情况。
• 验证存在多前置任务、需要取最大结束时间的情况。
• 验证依赖图中存在环时的无效输出。

验收清单

源文件：acceptance-checklist.md

• 正式题面、约束拆解、评分说明均已补齐
• 样例输入输出已定义并通过主实现校验
• python 主实现已提供并与样例输出对齐
• cpp 主实现已提供并与样例输出对齐
• 调试记录、决策记录、验证计划已补齐
• 可由 20-tools/assemble_case_dossiers.py 汇总为完整解题档案

样例输入输出

样例输入：sample.in

4
A 3 0
B 2 1 1
C 4 1 1
D 2 2 2 3

样例输出：sample.out

total_days=9
schedule=A:0-3|B:3-5|C:3-7|D:7-9

题解、建模与最终解法

自动整理的解题流程

• 题目主题：丝路科技传播：工期设计与工作量评估
• 题目摘要：根据任务工期和依赖关系计算最早开始时间与总工期，输出完整排程方案。
• 判题提示：该题以多项输出为主，重点是先算清楚每个指标，再统一整理输出顺序。
• 先完成输入、对象、约束和输出的四步建模，再落到具体算法和实现。
• 优先用样例验证最小流程，再补边界测试和错误分支。

解题思路

源文件：solution-rationale.md

1. 问题重述

根据任务工期和依赖关系计算最早开始时间与总工期，输出完整排程方案。

2. 数据结构与建模

• 主算法：拓扑排序 + 最早开始时间 DP
• 输入拆解后对应的数据结构要和输出项一一对应。
• 需要重点维护的状态包括：题目实体、核心指标、中间结果和最终答案。

3. 算法步骤

1. 根据依赖关系建立有向图和入度数组。
2. 把所有入度为 0 的任务按编号顺序加入队列。
3. 弹出任务时计算结束时间，并用它更新后继任务的最早开始时间。
4. 若处理任务数少于 n，说明存在环；否则输出总工期和排程。

4. 正确性说明

• 每一步都严格对应题面给出的规则或约束。
• 所有输出字段都来自同一份计算过程，不会出现“各算各的”的不一致情况。
• 边界情况通过单独分支或统一规则处理，保证程序在最小规模和重复值情况下也稳定。

5. 复杂度分析

• 复杂度取决于输入规模和主算法，但整体设计保持在初中组可讲解、可验证的范围内。
• 只保留必要状态，不引入超出题意的数据结构。

6. 易错点

• 多个任务都无前置依赖时可以同时从第 0 天开始。
• 某个任务可能依赖多个前置任务，开始时间要取最大结束时间。
• 若存在环，不能输出部分排程冒充最终答案。

7. 知识点清单

• 有向图依赖建模。
• 拓扑排序。
• 最早开始时间与最长路径思想。
• 入度维护。
• 循环依赖检测。

设计决策记录

源文件：decision-log.md

• 选择 拓扑排序 + 最早开始时间 DP 作为主算法，因为它能直接覆盖题目的核心约束。
• 题目核心是依赖约束，因此拓扑排序是最直接的主线。
• 最早开始时间可以在松弛后继任务时同步维护，不需要二次遍历。
• Python 与 C++ 版本统一输出格式，便于双语训练和证据采集。

验证计划

源文件：validation-plan.md

• 先验证题面公开样例，确保基础流程无误。
• 验证所有任务都无依赖的情况。
• 验证存在多前置任务、需要取最大结束时间的情况。
• 验证依赖图中存在环时的无效输出。
• 最后再补 1 组手工构造的极小数据，确认程序不会依赖特殊输入规模。

备选方案

源文件：alternatives.md

最终代码与实现

Python 主实现

源文件：main.py

• 实现状态：当前已有可执行实现

import heapq
import sys


def solve(data: str) -> str:
    tokens = data.split()
    if not tokens:
        return ""
    it = iter(tokens)
    n = int(next(it))
    names = [""] * (n + 1)
    duration = [0] * (n + 1)
    indegree = [0] * (n + 1)
    graph = [[] for _ in range(n + 1)]
    start = [0] * (n + 1)
    end = [0] * (n + 1)
    for task_id in range(1, n + 1):
        names[task_id] = next(it)
        duration[task_id] = int(next(it))
        k = int(next(it))
        for _ in range(k):
            pre = int(next(it))
            graph[pre].append(task_id)
            indegree[task_id] += 1
    heap = [task_id for task_id in range(1, n + 1) if indegree[task_id] == 0]
    heapq.heapify(heap)
    processed = 0
    while heap:
        task = heapq.heappop(heap)
        processed += 1
        end[task] = start[task] + duration[task]
        for nxt in graph[task]:
            if end[task] > start[nxt]:
                start[nxt] = end[task]
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                heapq.heappush(heap, nxt)
    if processed != n:
        return "total_days=-1\nschedule=INVALID"
    total_days = max(end)
    schedule = "|".join(
        f"{names[i]}:{start[i]}-{end[i]}" for i in range(1, n + 1)
    )
    return f"total_days={total_days}\nschedule={schedule}"


if __name__ == "__main__":
    sys.stdout.write(solve(sys.stdin.read()).strip())
    sys.stdout.write("\n")

C++ 对照实现

源文件：main.cpp

• 实现状态：当前已有可执行实现

#include <functional>
#include <iostream>
#include <queue>
#include <string>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) {
        return 0;
    }
    vector<string> names(n + 1);
    vector<long long> duration(n + 1, 0), start(n + 1, 0), finish(n + 1, 0);
    vector<int> indegree(n + 1, 0);
    vector<vector<int>> graph(n + 1);
    for (int task = 1; task <= n; ++task) {
        int k;
        cin >> names[task] >> duration[task] >> k;
        for (int i = 0; i < k; ++i) {
            int pre;
            cin >> pre;
            graph[pre].push_back(task);
            ++indegree[task];
        }
    }
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int task = 1; task <= n; ++task) {
        if (indegree[task] == 0) {
            pq.push(task);
        }
    }
    int processed = 0;
    while (!pq.empty()) {
        int task = pq.top();
        pq.pop();
        ++processed;
        finish[task] = start[task] + duration[task];
        for (int nxt : graph[task]) {
            if (finish[task] > start[nxt]) {
                start[nxt] = finish[task];
            }
            --indegree[nxt];
            if (indegree[nxt] == 0) {
                pq.push(nxt);
            }
        }
    }
    if (processed != n) {
        cout << "total_days=-1\n";
        cout << "schedule=INVALID\n";
        return 0;
    }
    long long total_days = 0;
    for (int i = 1; i <= n; ++i) {
        if (finish[i] > total_days) {
            total_days = finish[i];
        }
    }
    cout << "total_days=" << total_days << "\n";
    cout << "schedule=";
    for (int i = 1; i <= n; ++i) {
        if (i > 1) {
            cout << '|';
        }
        cout << names[i] << ':' << start[i] << '-' << finish[i];
    }
    cout << "\n";
    return 0;
}

代码执行与运行结果

最新成功运行

PY 运行输出摘录

total_days=9
schedule=A:0-3|B:3-5|C:3-7|D:7-9

CPP 运行输出摘录

total_days=9
schedule=A:0-3|B:3-5|C:3-7|D:7-9

全部运行记录索引

调试、修正与流程留痕

调试日志

源文件：debug-journal.md

失败案例目录

源文件：failure-catalog.md

编码过程记录

源文件：implementation-journal.md

全流程文件导航

• 题目总览：s3-jh-03-tech-schedule/README.md
• 题面与约束：official-prompt.md、parsed-constraints.md、scoring-model.md、acceptance-checklist.md
• 代码与样例：10-cases/s3-jh-03-tech-schedule/02-solution
• 运行证据：10-cases/s3-jh-03-tech-schedule/03-execution
• 调试过程：debug-journal.md、failure-catalog.md、implementation-journal.md
• 解法说明：solution-rationale.md、decision-log.md、validation-plan.md、alternatives.md
• 交付档案：final-report.md、appendix-code.md、appendix-runs.md、evidence-pack.md