52 lines
4.1 KiB
Markdown
52 lines
4.1 KiB
Markdown
# 源码说明
|
||
|
||
共 28 份独立完整程序。建议全部按 GCC C++17 编译。每个文件含独立 `main`，应单独编译。输入来自标准输入，结果写到标准输出。
|
||
|
||
## 前六份课件
|
||
|
||
| 文件 | 对应内容 | 输入与输出约定 |
|
||
| --- | --- | --- |
|
||
| 01_dijkstra_naive.cpp | P3371，邻接表朴素 Dijkstra | n m s；m 条有向边；输出源点到各点距离 |
|
||
| 01b_dijkstra_forward_star.cpp | P3371，前向星朴素 Dijkstra | 同上；改变存图方式 |
|
||
| 01c_dijkstra_path.cpp | 第一章路径恢复扩展 | 教学输入格式与路径输出见源码注释及第一章备注 |
|
||
| 02_dijkstra_heap.cpp | P3371，堆优化 Dijkstra | 同上；非负边权 |
|
||
| 02b_bellman_ford.cpp | 备份版 Bellman–Ford | 同 P3371 输入输出；教学扩展允许负边，无源点可达负环 |
|
||
| 02c_spfa.cpp | FIFO SPFA | 同上；此版不带判环，最坏 O(nm) |
|
||
| 03_flights.cpp | P4568，分层状态 | n m k；s t；m 条无向边；0 开始编号；不可达输出 -1 是教学扩展约定 |
|
||
| 03b_postman.cpp | P1629，反图与往返 | n m；m 条有向边；1 开始编号；按原题保证各点互达 |
|
||
| 03c_multi_source.cpp | 多源最短路教学扩展 | n m r；r 个源点；m 条有向边；不可达输出 -1 |
|
||
| 04_negative_cycle.cpp | P3385，SPFA 判环 | 多组数据；仅检测从 1 可达的负环；非负输入边双向、负边单向 |
|
||
| 04a_bf_negative.cpp | P3385，Bellman–Ford 判环 | 同上一文件 |
|
||
| 04b_difference_constraints.cpp | P5960，差分约束 | a b c 表示 x[a]−x[b]≤c；输出任意解，无解为 NO |
|
||
| 05_second_shortest.cpp | P2865，严格次短路 | 正权无向图；允许重复经过点边，第二距离严格大于最短距离 |
|
||
| 06_floyd_trip.cpp | P2910，规定访问顺序 | 读入访问序列和完整危险值矩阵，输出最小总危险值 |
|
||
| 06a_floyd_general.cpp | 通用 Floyd 教学模板 | n m；m 条有向边；无负环；输出矩阵，不可达为 INF |
|
||
| 06b_transitive_closure.cpp | B3611，非空路径闭包 | 输入邻接矩阵；不预先把对角线设为真 |
|
||
|
||
P3371 系列程序以 2147483647 表示不可达。通用 Floyd 教学模板建议 n≤500、边权绝对值≤10^9，确保所选 INF 和 `long long` 有足够余量。
|
||
|
||
## 综合习题的重要前提
|
||
|
||
`07_01_p1144.cpp` 至 `07_12_p2047.cpp` 与课程使用说明的 12 道习题一一对应，输入输出遵循相应题号。
|
||
|
||
- P1144：重边按不同边计数，模 100003。
|
||
- P1875：配方读到 EOF；保存同一原料对的不同产物，完全重复的无序配方去重。主算法 O(n²+R)，哈希去重的 O(R) 是期望复杂度。无关药水极大中间计数采用饱和运算，原题承诺范围内的目标答案保持精确。
|
||
- P1462：费用包括起终点，耗血恰好等于初始血量仍可行。
|
||
- P1073：传播次数的界依赖价格范围 1…100。
|
||
- P1993：全图判定约束可行性，所有点一起初始化。
|
||
- P3275：非递归强连通分量与缩点，避免深链递归栈溢出；总量用 `long long`。
|
||
- P6464：每次试装传送门都读取原图 Floyd 距离。
|
||
- P3403：从第 1 层开始计数，先排除不可达再计数，覆盖 h=2^63−1 边界。
|
||
- P1119：依赖原题重建时间、询问时间分别不降的保证；0 开始编号。
|
||
- P1037：允许零次变换，对角线置真；按最终数字去重，使用十进制高精度字符串。
|
||
- P2419：原题胜负关系无矛盾，检查是否与其余所有点可比较。
|
||
- P2047：正权简单无向图；有序点对双向累计并排除端点，使用 `long double` 计数与求比例，输出三位小数。
|
||
|
||
## 验证
|
||
|
||
本次以 C++17 重新编译第 2—7 章的 25 份程序，31 组新增教学输入及关键边界检查全部通过。输入输出见 `../教学样例/样例清单.json`，对应记录见 `../资料与核查/修订样例验证.json`。
|
||
|
||
第一章 3 份程序的修订验证记录另见 `../资料与核查/第一章程序核查.json`。旧版 27 份程序累计 3,972 组本地对照记录保留在 `../资料与核查/旧版程序验证`，本次没有重复执行全部历史测试。
|
||
|
||
所有验证均为本地编译运行，没有向在线评测提交。
|