『算法-ACM 竞赛-图论』模板整理合集

图论模板整理合集

还在持续更新， 模板还没发齐。最后更新时间：2019 年 12 月 6 日

由于 Github 不太友好，蒟蒻就把 PDF 放到了百度云里

链接：https://pan.baidu.com/s/1yuII_btZspV5GVhAtlcl0Q
提取码：vvfn

最短路：

SPFA 模板

Dijkstra 模板

Floyd 模板

图论–最短路–第 K 短路（IDA*）（IDA Star)模板

图论–最短路–dijkstra（含路径输出）模板

图论–最长路–基于 SPFA 的调整模板

传递闭包：

传递闭包

欧拉与哈密尔顿路径：

欧拉回路

图论–欧拉回路–弗罗莱算法模板

LCA：

图论–LCA–Tarjan（离线）

图论–LCA–树上倍增法（在线）

图论–LCA–在线 RMQ ST

最小环：

图论–最小环–Floyd 模板

树的直径：

图论–树的直径–DFS+树形 DP 模板

树的重心：

图论–树的重心（DFS） 模板

生成树：

图论–最小生成树–Kruscal 模板

图论–最短路径生成树（最小边权和）模板

图论–最短路径生成树计数–模板

图论–生成树–次小生成树模板

图论–曼哈顿距离最小生成树模板

图论–生成树计数模板

图论–最小生成树–Prim 算法（带边输出）模板

连通性：

图论–割点–Tarjan 模板

图论–割边–Tarjan 模板

图论–边双连通 V-DCC 缩点

图论–双连通 E-DCC 缩点模板

图论–强连通 SCC 缩点模板

二分图匹配：

图论–二分图最大匹配–匈牙利

图论–二分图最佳完美匹配–KM

一般图带花树匹配：

图论–一般图带花树匹配（缩点）

网络流：

最大流（EK）

最大流（Dinic 矩阵版）

最大流（Dinic 邻接表版）

最大流（Hlpp）

2-SAT:

2-SAT–暴力染色法求字典序最小模版

2-SAT–暴力染色法模板（字典序最小解) RQ 的板子

2-SAT–Tarjan 连通分量+拓扑排序 O(N+M）模板

拓扑排序：

图论–拓扑排序–判断是否为 DAG 图

差分约束：

图论–差分约束模板