系列索引：
最短路
Floyd
基本思路：枚举所有点与点的中点，如果从中点走最短，更新两点间距离值。时间复杂度 \(O(V^3 )\)。
int n, m, f[N][N];memset(f, 0x3f, sizeof(f));for (int i=1, a, b, w; i<=m; i++) { scanf("%d%d%d", &a, &b, &w); if (f[a][b]>w) f[a][b]=w, f[b][a]=w; //去重边}for (int k=1; k<=n; k++) for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) f[i][j]=min(f[i][j], f[i][k]+f[k][j]); Dijkstra (堆优化)
create vertex set \(Q\)
for each vertex \(v\) in Graph: $d(v)← \infty $ \(\text{prev}(v) ←\) NULL add \(v\) to \(Q\)\(d(\text{source}) ← 0\) while \(Q\) is not empty: \(u ←\) vertex in \(Q\) with min \(d(u)\) remove \(u\) from \(Q\) for each neighbor \(v\) of \(u\): \(alt ← d(u) + \text{length}(u,v)\) if \(alt < d(v)\): $d(v)← alt $ $\text{prev}(v) ← u $基本思路：更新每个点到原点的最短路径；寻找最短路径点进行下一次循环；循环次数达到 n - 1 次说明每个点到原点的最短路已成，停止程序。时间复杂度 \(O(E\log{E})\)。
struct node { int u, dis; bool operator < (const node &n) const {return dis>n.dis; }} t;priority_queue q;int d[N];bool v[N];memset(d, 0x3f, sizeof(d));d[s]=0, t.u=s; q.push(t);while (!q.empty()) { t=q.top(), q.pop(); if (v[t.u]) continue; v[t.u]=true; for (int i=head[t.u]; i; i=nex[i]) if (t.dis+w[i] 使用 Fibonacci 堆：时间复杂度 \(O(E+V\log{V})\)。
SPFA (Bellman-Ford 队列优化)
BFS-SPFA：
基本思路：更新每个点到原点的最短路径，保证「路径可变得更小的点」在队列中；队列空说明每个点到原点的最短路已成，停止程序。时间复杂度稀疏图 \(O(kE), k\approx 2\)，最坏 \(O(VE)\)。
int d[N], pre[N], enq[N];bool inq[N];queue q;memset(d, 0x3f, sizeof(d));q.push(s); d[s]=0; inq[s]=true; enq[s]++;while (!q.empty()) { int a=q.front(); q.pop(); inq[a]=false; for (int b=head[a]; b; b=nex[b]) if (d[a]+w[b] =n) {printf("负环!\n"); return; } // *判断负环 inq[to[b]]=true; } }} DFS-SPFA：
bool flag=false;void spfa(int u) { ins[u]=true; for (int i=head[u]; i; i=nex[i]) if (dis[u]+w[i] 关于 SPFA：
“它死了。” （）
考虑使用堆优化 SPFA：Dijkspfa！
把队列改成堆（例如优先队列）。注意到堆不会随着编号所对应的权值大小的改变而改变，存在很多冗余状态，此时应主动把堆顶冗余状态删除。
while (!q.empty() && q.top().dis > d[q.top().u]) q.pop(); if (q.empty()) break;注意，即使加入堆优化，SPFA 还是 SPFA，并不会变成 Dijkstra。（Dijkstra 比较贪心所以无法处理负权回路；SPFA 因为方便卡常，已经死了。）另外，对于最小费用最大流，还有一种实现 Dijkstra 处理负权回路的方式，参见 。
01 BFS：双端队列，0 加入队列前端，1 加入队列末端。时间复杂度 \(O(m )\)。
\(\sum w_i \le W\) BFS：桶 + 链表 代替堆。时间复杂度 \(O(m+W )\)。
差分约束
形如 \(x_i-x_j\ge -c_k\) 或 \(x_i+c_k\ge x_j\) 可以看作从 \(i\) 向 \(j\) 连一条长度为 \(c_k\) 的边，求最短路；存在负环则无解。
同理，形如 \(x_i-x_j\le -c_k\) 或 \(x_i+c_k\le x_j\) 也可以看作从 \(i\) 向 \(j\) 连一条长度为 \(c_k\) 的边，求最长路；存在正环则无解。
判断差分约束系统是否成立：以根节点出发遍历全图，不出现负环。如果图不联通，从超级源向每个节点引边权为 0 的边。
标准做法是使用 SPFA，但显然要用 Dijkstra。
\(k\) 短路
\(n\) 个点，\(m\) 条边，每条给出有向边并带有权值，给出 start，end 和 \(k\)，求 s~t 所有路径中的第 \(k\) 短路。
\[f(x)=g(x)+h(x)\]
\(f(x)\) 就是路径的长度；\(g(x)\) 是估价函数，我们选择 \(x\)~end 的最短路径；\(h(x)\) 是实际长度，start~\(x\) 的总路径长。
那么我们优先访问 \(f(x)\) 更加小的点：因为它更可能成为最短，再第二短，再……如果 end 被访问了 \(k\) 次了，那么目前得到的值 \(f(x)\) 就是 \(k\) 短路的长度。求 \(k\) 短路，要先求出最短路、次短路、第三短路、……、第 \((k-1)\) 短路，然后访问到第 \(k\) 短路。
预处理 \(g(x)\)：将所有边反向，然后求 end 到所有点的单源最短路径（Dijkstra）。
A* 启发式搜索。可以做成 BFS-A*，节点直接按照 \(f(x)\) 序访问。
最小生成树
Prim
基本思路：记录 \(f[i]\) 表示当前由已经选出来的最小生成树到 \(i\) 点的最小边是多少；每次就是找出还没有加进最小生成树的点中最小边最小的点，加进最小生成树，更新联结的点 \(f\) 值。时间复杂度 \(O(V^2 )\)。
Kruskal
sort \(E\)
\(MST←\varnothing\) let each point be independent connected component for each edge \(u\) in \(E\) if \(x_u\) and \(y_u\) on difference connected component add \(u\) to \(MST\) union \(x_u,y_u\)基本思路：按边长度从小到大排序，循环添加「不成环」的边；边数达到 \(n - 1\) 说明最小生成树已成，停止程序。时间复杂度 \(O(E\log{E})\)。
const int N = 1000 + 3, M = 20000 + 3;int dset[N], n, m;struct edge { int x, y, w; bool operator < (const edge &a) const { return w < a.w; }} edges[M];int find(int x) { return (dset[x]==-1) ? x : dset[x]=find(dset[x]); }void join(int x, int y) { if (find(x)!=find(y)) dset[find(x)]=find(y); }int Kruskal() { memset(dset, -1, sizeof(dset)); sort(edges+1, edges+m+1); int cnt=0, tot=0; for (int i=1; i<=m; i++) //循环所有已从小到大排序的边 if (find(edges[i].x)!=find(edges[i].y)) { // (因为已经排序，所以必为最小) join(edges[i].x, edges[i].y); // 相当于把边(u,v)加入最小生成树。 tot += edges[i].w; cnt++; if (cnt==n-1) break; // 说明最小生成树已经生成 } return tot;} Borůvka
基本思路：用定点数组记录每个子树的最近邻居。对于每一条边进行处理：如果这条边连成的两个顶点同属于一个集合，则不处理，否则检测这条边连接的两个子树，如果是连接这两个子树的最小边，则更新 (合并)。时间复杂度平均 \(O(V+E)\)，最坏 \(O((V+E)\log V)\)。（显然比 Kruskal 快）
struct node {int x, y, w; } edge[M];int d[N]; // 各子树的最小连外边的权值int e[N]; // 各子树的最小连外边的索引bool v[M]; // 防止边重复统计int fa[N];int find(int x) {return x==fa[x] ? x : (fa[x]=find(fa[x])); }void join(int x, int y) {fa[find(x)]=find(y); }int Boruvka() { int tot=0; for (int i=1; i<=n; ++i) fa[i]=i; while (true) { int cur=0; for (int i=1; i<=n; ++i) d[i]=inf; for (int i=1; i<=m; ++i) { int a=find(edge[i].x), b=find(edge[i].y), c=edge[i].w; if (a==b) continue; cur++; if (c 最近公共祖先
倍增求 LCA
基本思路：先把比较深的点跳到和比较浅的点同样高，然后两个点分别往上跳一格（可以看做同时往上跳），直到跳到相同的点为止。 记录 \(p[i][j]\)，表示从 \(i\) 号点往上跳 \(2^j\) 步到达哪个点。初始情况：\(p[i][0]\) 就是 \(i\) 点树上的父亲。即只记录一部分 \(j\)。如果要从 \(i\) 号点往上跳 \(k\) 步，就把 \(k\) 在二进制下分解成几个 2 的次幂，利用 \(p\) 就可以一次多跳几步。\(p\) 数组可以在预处理的时候顺便完成。\(p[i][j]=p\big[~p[i][j-1]~\big]\big[j-1\big]\)。时间复杂度预处理 \(O(n\log{n})\)，询问 \(O(q\log{n})\)。
int p[N][logN], dep[N];void dfs(int x) { for (int i=head[x]; i; i=nex[i]) if (to[i]!=p[x][0]) dep[to[i]]=dep[x]+1, p[to[i]][0]=x, dfs(to[i]);}inline void init() { dfs(s); for (int j=1; (1< <=n; j++) for (int i=1; i<=n; i++) p[i][j]=p[p[i][j-1]][j-1];}inline int lca(int x, int y) { if (dep[x] > dep[y]) swap(x, y); int f = dep[y] - dep[x]; for (int i=0; (1< <=f; i++) if ((1< =0; --i) if (p[x][i]!=p[y][i]) x=p[x][i], y=p[y][i]; return p[x][0];} DFS 序 + ST 表求 LCA
基本思路：欧拉序上的 RMQ。DFS 一遍求出欧拉序、每个点深度；对于一个固定的序列欧拉序，多次询问区间内最小的数及其位置。记 \(\text{RMQ}[i][j]\) 表示从 \(i\) 开始，长度为 \(2^j\) 区间内最小的数是多少，\(\text{RMQ}[i][j]=\min\{\text{RMQ}[i][j-1],\text{RMQ}[i+2^{j-1}][j-1]\}\)；为了求位置，再记个 \(\text{MinPos}[i][j]\)。 利用预处理的信息取两个长度均为 2 的次幂的区间使得其能覆盖 \([x,y]\)。
int v[N], d[N], mpos[N], dfn[N<<1], fn, RMQ[N<<1][log(N<<1)];void dfs(int x, int t) { v[x]=1, d[x]=t, mpos[x]=fn, dfn[fn++]=x; for (int i=head[x]; i; i=nex[i]) if (!v[to[i]]) dfs(to[i], t+1), dfn[fn++]=x;}inline void lca_init() { dfs(s, 0); for (int i=0; i y) swap(x, y); int k=log2(y-x+1); if (d[RMQ[x][k]]<=d[RMQ[y-(1< 树链剖分求 LCA
基本思路：选出每个点最“重”的儿子，就是子树大小最大的那个儿子，并将这条边标为“重边”，重边连成“重链”。 我们设 \(x\) 的重链链顶为 \(\text{Top}[x]\)。求 \(\text{LCA}(u,v)\)：注意一个点只有一个重儿子，所以 \(u\) 和 \(v\) 往祖先的两条路径，至少一条是从 \(\text{LCA}\) 出来的轻边。每次看看 \(\text{Top}[u]\) 和 \(\text{Top}[v]\) 哪个深度更大，如果是 \(u\)，就把 \(u\) 跳到 \(\text{Fa}[\text{Top}[u]]\)。直到两个点在同一条重链上，\(\text{LCA}\) 就是此时深度比较小的点。 时间复杂度 \(=\) 重链条数 \(O(\log{n})\)。
int son[N], fa[N], dep[N], siz[N], top[N];inline int lca(int x, int y) { while (top[x]!=top[y]) { if (dep[top[x]] < dep[top[y]]) swap(x, y); x=fa[top[x]]; } if (dep[x]>dep[y]) swap(x, y); return x;}void dfs1(int x, int f, int d) { dep[x]=d, fa[x]=f, siz[x]=1; int heavy=-1; for (rint i=head[x]; i; i=nex[i]) { int &y=to[i]; if (y==f) continue; dfs1(y, x, d+1); siz[x]+=siz[y]; if (siz[y]>heavy) son[x]=y, heavy=siz[y]; }}void dfs2(int x, int tp) { top[x]=tp; if (!son[x]) return; dfs2(son[x], tp); for (rint i=head[x]; i; i=nex[i]) { int &y=to[i]; if (y==fa[x] || y==son[x]) continue; dfs2(y, y); }}dfs1(root, 0, 1);dfs2(root, root);