当前位置：首页 > news >正文

CCF-CSP 202212-2 训练计划：拓扑排序双图解法，15ms 100分代码详解

news 2026/7/12 16:43:51

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; vector<int> p(m+1), t(m+1); for(int i=1; i<=m; i++) cin >> p[i]; for(int i=1; i<=m; i++) cin >> t[i];

1.2 图结构构建

我们需要构建两种图表示：

正向图：用于计算最早开始时间，边u→v表示v依赖于u
反向图：用于计算最晚开始时间，边v→u表示u被v依赖

vector<vector<int>> g(m+1), ginv(m+1); vector<int> in(m+1), out(m+1); for(int i=1; i<=m; 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，然后按照拓扑序递推：

vector<int> mn(m+1); queue<int> q; for(int i=1; i<=m; 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 i=1; i<=m; i++) cout << mn[i] << " \n"[i==m]; return; }

最晚开始时间采用反向拓扑排序，初始化所有不被依赖的任务的最晚开始时间为n - t[i] + 1：

vector<int> mx(m+1, INF); for(int i=1; i<=m; 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; vector<int> p(m+1), t(m+1); for(int i=1; i<=m; i++) cin >> p[i]; for(int i=1; i<=m; i++) cin >> t[i]; // 建图及统计度数 vector<vector<int>> g(m+1), ginv(m+1); vector<int> in(m+1), out(m+1); for(int i=1; i<=m; i++) { if(!p[i]) continue; g[p[i]].push_back(i); in[i]++; ginv[i].push_back(p[i]); out[p[i]]++; } // 计算最早开始时间 vector<int> mn(m+1); queue<int> q; for(int i=1; i<=m; 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 i=1; i<=m; i++) cout << mn[i] << " \n"[i==m]; // 检查可行性 if(max_end > n) return; // 计算最晚开始时间 vector<int> mx(m+1, INF); for(int i=1; i<=m; 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 i=1; i<=m; i++) cout << mx[i] << " \n"[i==m]; } 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 vector<vector<int>>& g) { for(int u=1; u<g.size(); u++) { cout << u << ": "; for(int v : g[u]) cout << v << " "; cout << endl; } }