课程简介
系统讲解《算法竞赛进阶指南》第0x60章 图论 中的所有知识点及例题。
本课程为 视频课。
本课程除常规的知识点外，着重讲解算法的灵活应用，以及解决问题的思考方式、思路的形成过程。
本课程难度介于AcWing 算法提高课 和 算法进阶课 之间。
适用人群：面向竞赛生，例如准备ACM、NOIP、NOI的同学。
录像、答疑和打卡 功能永久有效。
试听课：
关于习题、代码和笔记：
- 所有课上笔记和代码，可通过 “打卡” 页面底部的 “相关代码” 找到，通常是第一份（讲师ID: lydrainbowcat）。
讲师
《算法竞赛进阶指南》的作者 李煜东 同学。
时间安排
视频总共30小时。
费用
费用总共 180 元。
拼团优惠 149 元：
- 三人拼团报名每人优惠31元。
- 拼团方式：点击右上角“报名”后，选择“拼团报名”，付款后邀请好友即可。每个团有效时间为24小时，超过时间后订单自动取消，已付金额会自动退回原账户。
知识点
| 视频名称 | 视频包含知识点 |
|---|---|
| 6101 图的概念与存储方式 | 图的定义 邻接矩阵 邻接表 |
| 6102 单源最短路 Dijkstra算法+堆优化 | 单源最短路 Dijkstra算法 堆优化的Dijkstra算法 |
| 6103 单源最短路 Bellman-Ford与SPFA算法 | Bellman-Ford SPFA及其时间复杂度 针对SPFA的数据构造 |
| 6104 例题 Telephone Lines | 分层图最短路 |
| 6105 例题 最优贸易 | Dijktra算法不适用的情况 |
| 6106 例题 道路与航线 | 拓扑排序套堆优化Dijkstra |
| 6107 Floyd算法 任意两点间最短路+传递闭包+最小环 | Floyd算法 传递闭包 无向图最小环 |
| 6108 例题 Cow Relays | Floyd与动态规划的联系 任意两点间最短路的另一种算法 |
| 6201 最小生成树 Kruskal与Prim算法 | 最小生成树(MST) Kruskal算法 Prim算法 |
| 6202 例题 走廊泼水节 + 野餐规划 | 加边、删边对最小生成树的影响 根节点有度数限制的MST |
| 6203 例题 最优比率生成树 + 黑暗城堡 | 最短路径生成树 |
| 6204 最小树形图 | 最小树形图 朱刘算法 |
| 6301 树的直径的两种求法 | 两次BFS求树的直径 树形DP求树的直径 |
| 6302 例题 巡逻 | 树形直径求法的适用性 |
| 6303 例题 树网的核 | |
| 6304 最近公共祖先 | 最近公共祖先(LCA) 树上倍增求LCA Tarjan算法求LCA |
| 6305 树上差分 例题 闇の連鎖 | 树上差分(单值) |
| 6306 例题 雨天的尾巴 | 树上差分(数组) 线段树合并 |
| 6307 例题 天天爱跑步 | 树上差分(数组 区间减法) |
| 6308 例题 异象石 | LCA的综合应用 |
| 6309 例题 次小生成树 | 树上倍增的综合应用 |
| 6310 例题 疫情控制 | |
| 6401 基环树与仙人掌的直径 + 例题 | 基环树直径 仙人掌直径 |
| 6402 例题 创世纪 | 基环树DP |
| 6403 基环树与仙人掌两点间距离 | 基环树/仙人掌上倍增 |
| 6501 负环判定 例题 Sightseeing Cows | 负环的判定方法效率对比 |
| 6502 差分约束 例题 Intervals | 差分约束系统 |
| 6601 割点 桥 例题 BLO | Tarjan算法求割点、桥 |
| 6602 双连通分量 缩点 例题 Network | 点/边双连通分量的求法 缩点 |
| 6603 例题 Knights of the Round Table | |
| 6604 欧拉路问题 例题 Watchcow | 欧拉路/欧拉回路的判定与求法 |
| 6701 强连通分量 | Tarjan算法求强连通分量 |
| 6702 例题 Network of schools + 银河 | 强连通分量的缩点 |
| 6703 有向无环图必经边 例题 PKU ACM team’s excursion | 有向无环图的必经点、必经边求法 |
| 6704 2-SAT问题 | 2-SAT问题的判定、输出方案 |
| 6801 二分图判定 最大匹配 例题 棋盘覆盖 + 車的放置 | 二分图判定 二分图最大匹配 匈牙利算法 |
| 6802 多重匹配 例题 导弹防御塔 | 二分图多重匹配 |
| 6803 带权最大匹配 KM算法 例题 Ants | 二分图带权最大匹配 KM算法O(n^3) |
| 6901 二分图的最小覆盖与最大独立集 | 二分图最小点覆盖、最大独立集 |
| 6902 有向无环图的最小路径点覆盖 | 有向无环图最小路径覆盖及其方案 |
| 6A01 最大流的增广路与Dinic算法 | 最大流 EK算法 Dinic算法 时间复杂度分析 |
| 6A02 二分图的必须边和可行边 例题 舞动的夜晚 | 二分图的必须边与可行边 |
| 6A03 最小割 例题 Cable TV Network | 最小割 最大流最小割定理及证明 |
| 6A04 费用流 例题 K取方格数 | 费用流 EK算法及证明 |
课程交流
AcWing算法交流群：705158186
《算法竞赛进阶指南》读者群：650836280
