第一部分 网络流基础 #
1. 网络流基本概念 #
- 流网络定义与性质
- 容量函数与流量函数
- 可行流与最大流
- 残量网络概念
- 增广路径理论
- 流量守恒定律
- 流量值与割容量
2. 网络流模型 #
- 有向网络与无向网络
- 单源单汇网络
- 多源多汇网络
- 带下界流网络
- 费用流网络
- 动态流网络
- 多商品流网络
第二部分 经典最大流算法 #
1. Ford-Fulkerson方法 #
- 基本思想与框架
- 增广路径选择策略
- 算法正确性证明
- 时间复杂度分析
- 容量为整数时的性质
- 实际应用中的限制
2. Edmonds-Karp算法 #
- 最短增广路径策略
- BFS在算法中的应用
- O(VE²)时间复杂度证明
- 实现细节与优化
- 与其他算法的比较
3. Dinic算法 #
- 层次图概念
- 阻塞流计算
- 算法框架与流程
- O(V²E)时间复杂度
- 当前弧优化技术
- 实际性能分析
4. 其他最大流算法 #
- Push-Relabel算法族
- Goldberg-Tarjan算法
- ISAP算法
- 二分图匹配转化
- 单位容量网络特化算法
第三部分 最小割问题 #
1. 最小割理论 #
- 最大流最小割定理
- 割的定义与分类
- 割容量计算
- 最小割唯一性
- 全局最小割问题
2. 最小割算法 #
- Stoer-Wagner算法
- Gomory-Hu树构造
- 基于最大流的最小割计算
- 随机化算法
- 近似算法
第四部分 费用流问题 #
1. 最小费用最大流 #
- 费用网络定义
- 负环检测与处理
- 成功最短路算法
- 原始对偶算法
- 容量缩放技术
2. 费用流算法 #
- Bellman-Ford方法
- Dijkstra算法应用
- 势函数技术
- 最小平均圈消去
- 网络单纯形法
第五部分 特殊网络流问题 #
1. 带上下界流 #
- 可行流存在性判定
- 循环流问题
- 上下界最大流
- 上下界最小流
- 转化方法与技巧
2. 二分图匹配 #
- 最大匹配问题
- 匈牙利算法
- Hopcroft-Karp算法
- 带权匹配
- 稳定婚姻问题
3. 多商品流 #
- 问题定义与模型
- 线性规划方法
- 近似算法
- 整数多商品流
- 应用场景分析
第六部分 网络流应用 #
1. 图论应用 #
- 点连通度计算
- 边连通度计算
- 平面图分离器
- 图分解问题
- 路径覆盖问题
2. 组合优化应用 #
- 任务分配问题
- 资源分配问题
- 调度问题
- 运输问题
- 选址问题
3. 实际工程应用 #
- 通信网络设计
- 交通网络优化
- 电力系统调度
- 物流配送规划
- 社交网络分析
第七部分 高级专题 #
1. 动态网络流 #
- 时间扩展网络
- 动态最大流
- 动态最小割
- 在线算法
- 预测模型
2. 随机网络流 #
- 随机容量网络
- 概率流问题
- 期望最大流
- 鲁棒优化
- 随机算法
3. 并行与分布式算法 #
- 并行最大流算法
- 分布式计算模型
- MapReduce实现
- GPU加速技术
- 大规模网络处理
第八部分 算法实现与优化 #
1. 数据结构选择 #
- 邻接表与邻接矩阵
- 动态数组应用
- 优先队列使用
- 并查集优化
- 内存管理技巧
2. 性能优化技术 #
- 输入输出优化
- 缓存友好设计
- 向量化计算
- 预处理技术
- 启发式策略
3. 实际编码技巧 #
- 边界条件处理
- 调试与测试方法
- 代码模块化设计
- 性能分析工具
- 竞赛编程技巧