AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 问答
    • 吐槽
  • App
  • 登录/注册
《算法竞赛进阶指南》第0x60章作者李煜东亲讲     进行中 返回课程列表 使用激活码
 
参与人数:610      起止时间:长期
报名

  • 详情
  • 动态
  • 排行
  • 讨论

课程简介

系统讲解《算法竞赛进阶指南》第0x60章 图论 中的所有知识点及例题。
本课程为 视频课。

本课程除常规的知识点外,着重讲解算法的灵活应用,以及解决问题的思考方式、思路的形成过程。

本课程难度介于AcWing 算法提高课 和 算法进阶课 之间。
适用人群:面向竞赛生,例如准备ACM、NOIP、NOI的同学。

录像、答疑和打卡 功能永久有效。

试听课:

  1. 6101 图的概念与存储方式
  2. 6102 单源最短路 Dijkstra算法+堆优化
  3. 6103 Bellman-Ford与SPFA算法
  4. 6104 例题 Telephone Lines

关于习题、代码和笔记:

  • 所有课上笔记和代码,可通过 “打卡” 页面底部的 “相关代码” 找到,通常是第一份(讲师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

1024
x

© 2018-2023 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息