图论
本专题目录
- 删边最短路
- CF1163F Indecisive Taxi Fee
- 树上问题
- LCA
- tarjan离线求LCA
- 树链剖分HLD
- 树链剖分之重链剖分
- 树链剖分之长链剖分
- 树上启发式合并
- 拓扑排序
- 最小生成树
- prim算法
- kruskal算法
- kruskal重构树
- boruvka算法求最小生成树
- 斯坦纳树
- 最短路
- dijkstra $ O(n^2) $
- 堆优化的dijk
- SPFA
- spfa判负环
- johnson算法求带负权边的全源最短路
- 传递闭包(floyd)
- 最小环
- k短路 $ O(n^3logk) $
- 差分约束
- tarjan求强连通分量
- kosaraju算法(两次dfs求强连通分量)
- tarjan求点双连通分量
- tarjan求边双连通分量
- 动态维护边双连通分量
- 2-sat
- 2sat输出方案(n^2)
- 环计数问题
- 欧拉回路
- 【模板】欧拉路径(有向图输出字典序最小)
- 染色法判断二分图
- 匈牙利算法求解二分图
- 二分图最大权匹配（MaxAssignment 基于KM）
- Hopcroft-karp 算法
- 一般图最大匹配
- 相关应用
- 最小点覆盖：每条边都有一个点被选
- 最大独立集：选出最多的点集，使得内部没有边
- 最小路径点覆盖：用最少的互不相交的路径将点覆盖
- 最小路径重复点覆盖：路径可以相交
- 最小环
- 网络流
- Edmonds-Karps算法$ O(nm^2)(能处理10^3-10^4规模的网络) $
- Dinic算法 $ O(n^2m)(能处理10^4-10^5规模的网络) $
- Dinic封装版
- 最小费用最大流
- 费用流封装版
- 最大费用最大流
- 有上下界费用流
- 有源汇上下界费用流
- 图论问题trick
- 最小直径生成树
- 同余最短路
- Stoer-Wagner算法(求无向图最小割)
- 二分图最大权匹配
- 一般图最大匹配(带花树算法)
- Prufer序列
- LGV引理(有向无环图不相交路径计数)
- 支配树
- 线段树动态维护树的直径
- k短路
- 矩阵树定理
- tarjan求差分约束
- 圆方树