CCF-CSP 202212-2 训练计划拓扑排序双图解法与高效实现策略在CCF-CSP认证考试中第二题往往考察考生对基础算法和数据结构灵活应用的能力。2022年12月的第二题训练计划就是一个典型的需要拓扑排序技巧的问题。本文将深入解析如何利用正反双图拓扑排序来计算任务的最早和最晚开始时间并提供一份15ms内完成的高效C实现代码。1. 问题分析与建模训练计划问题可以抽象为一个有向无环图(DAG)的任务调度模型。每个训练科目对应图中的一个节点科目间的依赖关系构成图中的有向边。题目要求我们计算两项关键指标最早开始时间每个任务在所有前置任务完成后能够开始的最早时间最晚开始时间在不影响总工期的前提下每个任务可以开始的最晚时间1.1 输入数据解析输入包含三行关键信息第一行n总天数和m科目数量第二行m个整数表示每个科目依赖的前置科目0表示无依赖第三行m个正整数表示每个科目需要的训练天数int n, m; cin n m; vectorint p(m1), t(m1); for(int i1; im; i) cin p[i]; for(int i1; im; i) cin t[i];1.2 图结构构建我们需要构建两种图表示正向图用于计算最早开始时间边u→v表示v依赖于u反向图用于计算最晚开始时间边v→u表示u被v依赖vectorvectorint g(m1), ginv(m1); vectorint in(m1), out(m1); for(int i1; im; i) { if(!p[i]) continue; g[p[i]].push_back(i); // 正向图 in[i]; // 入度统计 ginv[i].push_back(p[i]); // 反向图 out[p[i]]; // 出度统计 }2. 拓扑排序与时间计算2.1 最早开始时间计算最早开始时间采用正向拓扑排序初始化所有无依赖任务的开始时间为1然后按照拓扑序递推vectorint mn(m1); queueint q; for(int i1; im; i) { if(!in[i]) { mn[i] 1; // 无依赖任务第1天开始 q.push(i); } } int max_end 0; while(!q.empty()) { int u q.front(); q.pop(); for(int v : g[u]) { mn[v] max(mn[v], mn[u] t[u]); // 关键递推式 if(--in[v] 0) q.push(v); } max_end max(max_end, mn[u] t[u] - 1); }2.2 可行性检查与最晚时间计算在计算最晚时间前需要检查所有任务是否能在n天内完成if(max_end n) { // 只输出最早时间 for(int i1; im; i) cout mn[i] \n[im]; return; }最晚开始时间采用反向拓扑排序初始化所有不被依赖的任务的最晚开始时间为n - t[i] 1vectorint mx(m1, INF); for(int i1; im; i) { if(!out[i]) { mx[i] n - t[i] 1; // 最后时刻开始 q.push(i); } } while(!q.empty()) { int u q.front(); q.pop(); for(int v : ginv[u]) { mx[v] min(mx[v], mx[u] - t[v]); // 关键递推式 if(--out[v] 0) q.push(v); } }3. 完整代码实现与优化以下是整合了所有优化技巧的完整实现包含输入输出优化和简洁的逻辑处理#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; void solve() { int n, m; cin n m; vectorint p(m1), t(m1); for(int i1; im; i) cin p[i]; for(int i1; im; i) cin t[i]; // 建图及统计度数 vectorvectorint g(m1), ginv(m1); vectorint in(m1), out(m1); for(int i1; im; i) { if(!p[i]) continue; g[p[i]].push_back(i); in[i]; ginv[i].push_back(p[i]); out[p[i]]; } // 计算最早开始时间 vectorint mn(m1); queueint q; for(int i1; im; i) { if(!in[i]) { mn[i] 1; q.push(i); } } int max_end 0; while(!q.empty()) { int u q.front(); q.pop(); for(int v : g[u]) { mn[v] max(mn[v], mn[u] t[u]); if(--in[v] 0) q.push(v); } max_end max(max_end, mn[u] t[u] - 1); } // 输出最早时间 for(int i1; im; i) cout mn[i] \n[im]; // 检查可行性 if(max_end n) return; // 计算最晚开始时间 vectorint mx(m1, INF); for(int i1; im; i) { if(!out[i]) { mx[i] n - t[i] 1; q.push(i); } } while(!q.empty()) { int u q.front(); q.pop(); for(int v : ginv[u]) { mx[v] min(mx[v], mx[u] - t[v]); if(--out[v] 0) q.push(v); } } // 输出最晚时间 for(int i1; im; i) cout mx[i] \n[im]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }4. 算法复杂度与优化分析4.1 时间复杂度该算法的时间复杂度主要由以下部分组成建图O(m)正向拓扑排序O(m)反向拓扑排序O(m)总时间复杂度为O(m)非常高效可以轻松处理题目给出的m≤100的限制。4.2 空间复杂度空间消耗主要来自存储正向图和反向图O(m)存储入度和出度数组O(m)存储最早和最晚时间数组O(m)总空间复杂度也是O(m)。4.3 关键优化技巧双图结构同时维护正向图和反向图避免重复计算依赖关系拓扑排序队列复用使用同一个队列进行正反两次拓扑排序输入输出优化使用ios::sync_with_stdio(false)加速IO边界条件处理及时检查总工期是否满足要求5. 常见错误与调试技巧在实现这类拓扑排序问题时容易出现以下几种典型错误环状依赖检测虽然题目保证依赖关系合法但在实际应用中需要检测环时间计算错误注意开始时间和结束时间的转换结束时间开始时间持续时间-1初始化遗漏忘记初始化无依赖任务的最早开始时间为1反向图构建错误容易混淆边的方向调试时可以打印中间结果如图结构、度数数组对小样例手动计算验证检查边界条件如所有任务都无依赖的情况// 调试打印图结构示例 void printGraph(const vectorvectorint g) { for(int u1; ug.size(); u) { cout u : ; for(int v : g[u]) cout v ; cout endl; } }6. CSP考试实战建议针对CCF-CSP认证考试中的类似问题建议采取以下策略快速建模迅速将实际问题转化为图论模型模板准备提前准备好拓扑排序等常用算法的模板代码分步验证先确保部分正确性如最早时间计算正确时间管理第二题通常需要30-45分钟内完成极端测试考虑m1、所有任务无依赖等边界情况提示在考试中如果时间紧张可以先确保最早时间的计算正确这部分通常占50%的分数。最晚时间的计算可以作为加分项。7. 扩展应用与变种思考这种双图拓扑排序的方法不仅适用于训练计划问题还可以解决许多类似的调度问题课程安排计算课程的最早和最晚开课时间项目计划确定关键路径和任务浮动时间依赖解析软件包管理中的依赖关系处理并行任务调度确定任务的最优执行顺序变种问题可能包括带权重的依赖关系任务间的多种约束类型资源限制下的调度动态依赖关系变化掌握这种双图拓扑排序的思想能够帮助我们在面对复杂依赖关系时高效计算出各项任务的时间窗口为决策提供有力支持。
CCF-CSP 202212-2 训练计划拓扑排序双图解法与高效实现策略在CCF-CSP认证考试中第二题往往考察考生对基础算法和数据结构灵活应用的能力。2022年12月的第二题训练计划就是一个典型的需要拓扑排序技巧的问题。本文将深入解析如何利用正反双图拓扑排序来计算任务的最早和最晚开始时间并提供一份15ms内完成的高效C实现代码。1. 问题分析与建模训练计划问题可以抽象为一个有向无环图(DAG)的任务调度模型。每个训练科目对应图中的一个节点科目间的依赖关系构成图中的有向边。题目要求我们计算两项关键指标最早开始时间每个任务在所有前置任务完成后能够开始的最早时间最晚开始时间在不影响总工期的前提下每个任务可以开始的最晚时间1.1 输入数据解析输入包含三行关键信息第一行n总天数和m科目数量第二行m个整数表示每个科目依赖的前置科目0表示无依赖第三行m个正整数表示每个科目需要的训练天数int n, m; cin n m; vectorint p(m1), t(m1); for(int i1; im; i) cin p[i]; for(int i1; im; i) cin t[i];1.2 图结构构建我们需要构建两种图表示正向图用于计算最早开始时间边u→v表示v依赖于u反向图用于计算最晚开始时间边v→u表示u被v依赖vectorvectorint g(m1), ginv(m1); vectorint in(m1), out(m1); for(int i1; im; i) { if(!p[i]) continue; g[p[i]].push_back(i); // 正向图 in[i]; // 入度统计 ginv[i].push_back(p[i]); // 反向图 out[p[i]]; // 出度统计 }2. 拓扑排序与时间计算2.1 最早开始时间计算最早开始时间采用正向拓扑排序初始化所有无依赖任务的开始时间为1然后按照拓扑序递推vectorint mn(m1); queueint q; for(int i1; im; i) { if(!in[i]) { mn[i] 1; // 无依赖任务第1天开始 q.push(i); } } int max_end 0; while(!q.empty()) { int u q.front(); q.pop(); for(int v : g[u]) { mn[v] max(mn[v], mn[u] t[u]); // 关键递推式 if(--in[v] 0) q.push(v); } max_end max(max_end, mn[u] t[u] - 1); }2.2 可行性检查与最晚时间计算在计算最晚时间前需要检查所有任务是否能在n天内完成if(max_end n) { // 只输出最早时间 for(int i1; im; i) cout mn[i] \n[im]; return; }最晚开始时间采用反向拓扑排序初始化所有不被依赖的任务的最晚开始时间为n - t[i] 1vectorint mx(m1, INF); for(int i1; im; i) { if(!out[i]) { mx[i] n - t[i] 1; // 最后时刻开始 q.push(i); } } while(!q.empty()) { int u q.front(); q.pop(); for(int v : ginv[u]) { mx[v] min(mx[v], mx[u] - t[v]); // 关键递推式 if(--out[v] 0) q.push(v); } }3. 完整代码实现与优化以下是整合了所有优化技巧的完整实现包含输入输出优化和简洁的逻辑处理#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; void solve() { int n, m; cin n m; vectorint p(m1), t(m1); for(int i1; im; i) cin p[i]; for(int i1; im; i) cin t[i]; // 建图及统计度数 vectorvectorint g(m1), ginv(m1); vectorint in(m1), out(m1); for(int i1; im; i) { if(!p[i]) continue; g[p[i]].push_back(i); in[i]; ginv[i].push_back(p[i]); out[p[i]]; } // 计算最早开始时间 vectorint mn(m1); queueint q; for(int i1; im; i) { if(!in[i]) { mn[i] 1; q.push(i); } } int max_end 0; while(!q.empty()) { int u q.front(); q.pop(); for(int v : g[u]) { mn[v] max(mn[v], mn[u] t[u]); if(--in[v] 0) q.push(v); } max_end max(max_end, mn[u] t[u] - 1); } // 输出最早时间 for(int i1; im; i) cout mn[i] \n[im]; // 检查可行性 if(max_end n) return; // 计算最晚开始时间 vectorint mx(m1, INF); for(int i1; im; i) { if(!out[i]) { mx[i] n - t[i] 1; q.push(i); } } while(!q.empty()) { int u q.front(); q.pop(); for(int v : ginv[u]) { mx[v] min(mx[v], mx[u] - t[v]); if(--out[v] 0) q.push(v); } } // 输出最晚时间 for(int i1; im; i) cout mx[i] \n[im]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }4. 算法复杂度与优化分析4.1 时间复杂度该算法的时间复杂度主要由以下部分组成建图O(m)正向拓扑排序O(m)反向拓扑排序O(m)总时间复杂度为O(m)非常高效可以轻松处理题目给出的m≤100的限制。4.2 空间复杂度空间消耗主要来自存储正向图和反向图O(m)存储入度和出度数组O(m)存储最早和最晚时间数组O(m)总空间复杂度也是O(m)。4.3 关键优化技巧双图结构同时维护正向图和反向图避免重复计算依赖关系拓扑排序队列复用使用同一个队列进行正反两次拓扑排序输入输出优化使用ios::sync_with_stdio(false)加速IO边界条件处理及时检查总工期是否满足要求5. 常见错误与调试技巧在实现这类拓扑排序问题时容易出现以下几种典型错误环状依赖检测虽然题目保证依赖关系合法但在实际应用中需要检测环时间计算错误注意开始时间和结束时间的转换结束时间开始时间持续时间-1初始化遗漏忘记初始化无依赖任务的最早开始时间为1反向图构建错误容易混淆边的方向调试时可以打印中间结果如图结构、度数数组对小样例手动计算验证检查边界条件如所有任务都无依赖的情况// 调试打印图结构示例 void printGraph(const vectorvectorint g) { for(int u1; ug.size(); u) { cout u : ; for(int v : g[u]) cout v ; cout endl; } }6. CSP考试实战建议针对CCF-CSP认证考试中的类似问题建议采取以下策略快速建模迅速将实际问题转化为图论模型模板准备提前准备好拓扑排序等常用算法的模板代码分步验证先确保部分正确性如最早时间计算正确时间管理第二题通常需要30-45分钟内完成极端测试考虑m1、所有任务无依赖等边界情况提示在考试中如果时间紧张可以先确保最早时间的计算正确这部分通常占50%的分数。最晚时间的计算可以作为加分项。7. 扩展应用与变种思考这种双图拓扑排序的方法不仅适用于训练计划问题还可以解决许多类似的调度问题课程安排计算课程的最早和最晚开课时间项目计划确定关键路径和任务浮动时间依赖解析软件包管理中的依赖关系处理并行任务调度确定任务的最优执行顺序变种问题可能包括带权重的依赖关系任务间的多种约束类型资源限制下的调度动态依赖关系变化掌握这种双图拓扑排序的思想能够帮助我们在面对复杂依赖关系时高效计算出各项任务的时间窗口为决策提供有力支持。
