原来我没学过图论。
尝试把普及组+提高组的大部分图论内容重学。
定义啥的不写了。OI-Wiki 有详细的。
图的存储
一般来说有 3 种存图方法：
-
直接存。例如
struct Edge { int a, b, w; }edges[N];。 -
邻接矩阵。即一个矩阵 \(g\)，其中 \(g_{i, j}\) 表示 \(i, j\) 间的边数。如果无重边或重边无影响则 \(g\) 可以用
bool存储。 -
邻接表。存储以每个点为起点的所有边。一般两种写法：
-
vector<int> g[N]。动态数组。如果有边权可以vector<pair<int, int>> g[N]。 -
链式前向星。
// 初始化 int h[N], e[M], ne[M], we[M], idx; memset(h, -1, sizeof h); idx = 0; // 加边 void add(int a, int b, int c) { e[idx] = b, ne[idx] = h[a], we[idx] = c, h[a] = idx ++ ; } // 访问以 u 为起点的所有出边 (u, v, w) for (int i = h[u]; ~i; i = ne[i]) { int v = e[i], w = w[i]; }其中，
e[i], we[i]分别表示边-\(i\) 指向的点以及边权。h[i]表示当前点-\(i\) 的所有出边中最大的边的编号。ne[i]表示上一条与边-\(i\) 有相同起点的边。
-
其中：
- 直接用数组存一般会在 Kruskal 等需要将边按边权排序时使用。
- 邻接矩阵一般会在 Floyd 等平方及以上的算法中使用。
- 邻接表的存图方法最常见，可用于除上述情况外几乎所有情景。两种邻接表的优劣分别是：
vector：- 最好写的存图方法。
- 可以快捷的将点的所有出边排序。
vector内部常数较大，可能被毒瘤出题人卡常。
- 链式前向星：
- 代码较复杂，不过可以背下来。
- 只能按照边加入的时间从晚到早遍历。
- 常数略小。
最短路
给定一张有向图（无向图可以拆成两条有向边），边有边权。你需要求解源点到汇点的最短路。也就是你需要找一条从源点到汇点的路径，使得路径上边权和最小。
根据源点/汇点的数量，可将最短路算法归成两类：
- 多源汇最短路。即源点汇点有多个，你需要求任意一个源点到任意一个汇点的最短路。特别的，Floyd，Johnson 算法中，源点、汇点集合均为点集全集。
- 单源（多汇）最短路。即源点只有一个，你需要求从这个源点出发，到每个汇点的最短路。特别的，Dijkstra，Bellman-Ford 算法中，汇点集合是点集全集。
注意到我们省去了单源单汇和多源单汇。其中：
- 单源单汇最短路存在没有意义。因为单源最短路完全包含它。
- 多源单汇可以通过建反图的方式转化成单源多汇。
我们将按照这种分类介绍三种常见的最短路算法。
Floyd（多源汇最短路）
Floyd 是一种基于 DP 的算法。它的代码量最小，但是效率也最低。
设 \(f(u, v, k)\) 表示若我们只通过编号为 \(1 \sim k\) 的点（\(u, v\) 不受此限制），\(u \rightsquigarrow v\) 的最短路。
考虑转移。
若最短路不经过 \(k\)，也就是所有中途的点编号均为 \(1 \sim k -1\)。那么应该从 \(f(u, v, k - 1)\) 转移过来。
否则，若最短路经过 \(k\)，也就是我们先通过 \(1 \sim k - 1\) 的点从 \(u\) 到 \(k\)，再通过 \(1 \sim k - 1\) 的点从 \(k\) 到 \(v\)。那么应该从 \(f(u,k,k-1)+f(k,v,k-1)\) 转移过来。
综上：
\[f(u, v, k) = \min\{ f(u, v, k - 1), f(u,k-1,k) \} \]for (int i = 1; i <= n; ++ i )
for (int j = 1; j <= n; ++ j )
f[i][j] = i == j ? 0 : INF;
for (auto edge : edges) {
f[0][edge.from][edge.to] = min(f[0][edge.from][edge.to], edge.weight);
}
for (int k = 1; k <= n; ++ k )
for (int i = 1; i <= n; ++ i )
for (int j = 1; j <= n; ++ j )
f[k][i][j] = min(f[k - 1][i][j], f[k - 1][i][k] + f[k - 1][k][j]);
Dijkstra（单源最短路）
不妨设起点为 \(s\)。
令 \(s\) 到 \(u\) 的真实最短路是 \(D_u\)，目前已经找到的最短路是 \(d_u\)。也就是说我们希望最终 \(d_u = D_u\)。初始化 \(d_s = 0\)，其余 \(d_i = +\infty\)。
我们定义 松弛 一条边 \((u, v, w)\) 是指，通过 \(s \rightsquigarrow u\) 的最短路以及 \(u \to v\) 这条边更新 \(s \rightsquigarrow v\) 的最短路，即 \(\operatorname{checkmin}(d_v, d_u + w)\)。
将所有点分成两个集合。集合 \(S_1\) 存储所有已经找到最短路的点，\(S_2\) 存储未找到最短路的点。即 \(S_1 = \{u \mid d_u = D_u\}\)，\(S_2 = \{u \mid d_u \ne D_u\}\)。初始 \(S_1 = \{s\},S_2 = V - \{s\}\)。
算法流程是这样的：
-
取出 \(S_1\) 中 \(d\) 最小的点。设其为 \(u\)。在 \(S_1\) 中删除 \(u\)，并在 \(S_2\) 中加入 \(u\)。换言之我们断言 \(d_u= D_u\)。
-
松弛 \(u\) 的所有出边。
-
若 \(S_1\) 不为空，回到步骤 1。不难发现我们会执行 \(n\) 次这个流程。
为什么这样做是正确的？
不难发现我们只需要证明步骤 1 中取出的 \(u\) 是满足 \(d_u = D_u\)。考虑证明这一点。
读者自证不难。
如何快速取出 \(S_1\) 中 \(d\) 最小的点？优先队列即可。
时间复杂度 \(\mathcal O(m \log m)\)。
模板题 代码：
vector<int> get_dis(int s) {
vector<int> dis(n, INF); vector<bool> st(n, false);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
q.push({0, s}), dis[s] = 0;
while (q.size()) {
int u = q.top().second; q.pop();
if (st[u]) continue; st[u] = true;
for (Edge v : g[u])
if (dis[v.to] > dis[u] + v.w)
dis[v.to] = dis[u] + v.w, q.push({dis[v.to], v.to});
}
return dis;
}
值得说明的是，Dijkstra 只有在无负权边的基础上可以得到正确结果。
Bellman-Ford（单源最短路）
所以有负权边的图的最短路怎么求？Bellman-Ford。
Bellman-Ford 算法的精髓在于上面提到过的松弛操作。
如果图中没有负权回路（即边权和为负的回路，下称负环），那么 \(s\) 到任意点的最短路径中经过的边数一定 \(\le n - 1\)。这是因为，如果边数 \(\ge n\)，那么点数必 \(\ge n + 1\)，根据鸽巢原理一定存在至少一个节点被重复经过 \(\ge 2\) 次，也就是存在一个环。而因为图中没有负环，所以如果我们在路径上把这个环去掉，新路径的边权和一定比原路径更小。这与原路径最小矛盾。
所以我们可以对图中所有边松弛 \(n - 1\) 轮。或者说，我们重复对所有边松弛，直到没有节点的最短距离被更新时停止。而根据上面所说，在没有负环的情况下，我们最多松弛 \(n - 1\) 轮。此时就能得到每个点的真实最短路了。
正确性是显然的。时间复杂度 \(\mathcal O(nm)\)。
代码：
vector<int> get_dis(int s) {
vector<int> dis(n, INF);
dis[s] = 0;
for (int i = 0; i < n - 1; ++ i )
for (Edge e : edges)
dis[e.to] = min(dis[e.to], dis[e.from] + e.w);
return dis;
}
Bellman-Ford 的优化：SPFA
若 SPFA 是标算的一部分，题目不应当给出 Bellman–Ford 算法无法通过的数据范围。—— OI-Wiki
所以 SPFA 不用学（？）
注意到如果上一轮松弛中，点 \(u\) 的最短距离没有发生变化，那么在新一轮的松弛里松弛 \(u\) 的出边就没有意义了。
所以我们用队列存储所有松弛后最短距离发生变化的点，每次只松弛队列内的点。类似 BFS。
时间复杂度 \(\mathcal O(kn)\)，其中 \(k\) 是一个较小的常数。出题人可以轻易将 \(k\) 卡到 \(m\) 使 SPFA 死去。
vector<int> get_dis(int s) {
vector<int> dis(n, INF);
vector<bool> in_queue(n, false);
queue<int> q;
dis[s] = 0; q.push(s); in_queue[s] = true;
while (q.size()) {
int u = q.front();
q.pop();
for (Edge v : g[u])
if (dis[v.to] > dis[u] + v.w) {
dis[v.to] = dis[u] + v.w;
if (!in_queue(v.to)) q.push(v.to), in_queue(v.to) = true;
}
}
return dis;
}