OI 知识总览 算法篇 之图论

OI 复习 图论

一) 最小生成树

算法

1. Prim : $O((n+m)\log m)$ (堆优化)
2. Kruskal : $O(m\log m + m \alpha(n))$ (并查集优化)

题目

1. 新的开始
2. 【模板】严格次小生成树
3. [JSOI2008]最小生成树计数
4. CF891C Envy

二) 最短路

算法

1. Floyed : $O(n^3)$ 多源 最小环
2. Dijkstra : $O((n+m) \log m)$ 单源 优先队列 不能处理负边权
3. SPFA (已死) : $O(magic)$ 单源 判负环

题目

1. 十二桥问题

三) 强连通分量

算法

Tarjan : $O(n+m)$

四) 割点和桥 (不熟悉)

算法

Tarjan

五) 查分约束 (不熟悉)

算法

根据限制条件建边, 跑最短/最长路.

题目

1. [SCOI2011]糖果

六) 欧拉回路

欧拉回路 学习笔记 现学现卖