「学习笔记」图论入门算法

本文主要介绍了一些图论的简单入门算法，并附带模板和例题。

主要包括：图论概念，拓扑排序，最短路，双连通分量，强连通分量，最小生成树，拟阵

难度由浅入深，适合 $普及 \sim 提高$ 的选手观看，也欢迎新手来入门，大佬来指导！

$\mathcal{Part \ 1}$：一些概念：

图：一张图 $G$ 由点和边构成，点集为 $V$，边集为 $E$，记 $G=(V,E)$。若无特殊说明，$V = {1,2,\dots,n}$，$|E| = m$。

阶：图的点数 $n$，记作 $|G|$。

有向图与无向图：无向图中 $e \in E$ 没有方向，记作 $e=(u,v)$，为无序对。有向图中 $e \in E$ 有方向，记作 $e = u \to v$ 或有序对 $(u,v)$。

重边与自环：$E$ 中完全相同的两条边称为重边，连接相同点的边称为自环。

相邻：若 $(u,v) \in E$ 则称 $u,v$ 相邻。

邻边 / 出边 / 入边：无向图中与 $u$ 相连的边 $(u,v)$ 称为 $u$ 的邻边；有向图中从 $u$ 出发的边 $u \to v$ 称为 $u$ 的出边，到达 $u$ 的边 $v \to u$ 称为 $u$ 的入边。在之后的描述中，我们认为无向图的出边就是邻边。

途径：连接一串相邻结点的序列称为途径，记为 $v_0 \to v_1 \to \dots \to v_k$，满足 $(v_i, v_{i+1}) \in E$。

迹：不经过重复边的途径。

回路：$v_0 = v_k$ 的迹。

路径：所有点互不相同的途径，也称简单路径。

环：除 $v_0 = v_k$ 外所有点互不相同的途径。

联通：无向图中存在 $v_0 = u, v_k = v$ 的途径则 $u, v$ 联通。

弱联通：有向图改为无向图后 $u, v$ 联通则称 $u, v$ 弱联通。

连通图：任意两点连通的无向图。

弱连通图：任意两点弱连通的有向图。

可达：有向图存在 $v_0 = u, v_k = v$ 的途径，记作 $u \rightsquigarrow v$ 。

简单图：不含重边和自环的图。

有向无环图：不含环的有向图，简称 DAG。

完全图：任意不同的两点之间恰有一条边的无向简单图。

树：不含环的无向连通图。满足 $n = m + 1$ 。若干棵（包括一棵）树组成的连通块称为森林。

稀疏图 / 稠密图：$m$ 远小于 $n^2$ 的图称为稀疏图，$m$ 接近 $n^2$ 的图称为稠密图。

平面图：能画在平面上，满足除顶点处以外无边相交的图。

子图：满足 $V’ \subseteq V, E’ \subseteq E$ 且 $E’$ 两端都在 $V’$ 中的 $G’ = (V’, E’)$ 称为 $G$ 的子图。

导出子图：选择点集 $S$ 以及所有两端都在点集内的边构成的子图，记作 $G[V’]$ 。

生成子图：$|V’| = |V|$ 的子图。

极大子图（分量）：满足某性质的极大子图 $G’$，不存在同样满足此性质的子图 $G’’$ 使得 $G’ \subsetneqq G’’ \subseteq G$ 。极大联通子图也就是连通分量，或者连通块。

$\mathcal{Part\ 2}$ ：拓扑排序（Topological Sorting）

$\mathcal{Part\ 2.1}$：Kahn

$\text{Problem}$：给定 DAG $G=(V,E)$ ，要求出一个 $1\sim n$ 的排列 $p$， 设 $q_i$ 为 $i$ 在 $p$ 中的位置，满足 $u\to v \in E$，$q_u<q_v$。

题目就是说在访问任意一个点 $u$ 之前，已经访问过 $u$ 的所有入边的点。

我们考虑先访问所有入度为 $0$ 的点（这样的点可以理解为没有访问限制），将这些点插入队列 $Q$，每次取出当前队头 $u$ ，遍历 $u$ 的所有出边，如果连向的点 $v$ 入度为 $1$，由于我们已经访问过 $u$ ，所以 $v$ 的限制以经全部满足，将 $v$ 插入队列，并将 $v$ 的入度 $-1$，反之如果 $v$ 的入度不为 $1$ ，那么只将 $v$ 的入度 $-1$ 即可。

如果最后存在没有被访问的点，证明该图的拓扑序不存在。时间复杂度 $\mathcal{O}(n+m)$。

代码如下：

//使用手写队列实现，便于输出答案，也可选择 STL 中的 queue。
void Toposort(){
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++)
        if (!du[i]) q[++tt] = i;
    while (hh <= tt){
        int u = q[hh++];
        for (int i = h[u]; i; i = ne[i]){
            if (!--du[e[i]])
                q[++tt] = e[i];
        }
    }
    for (int i = 0; i <= tt; i++)
        cout << q[i] << " ";
}

$\mathcal{Part \ 2.2}$：例题详解

$\mathcal{A}$：B3644 【模板】拓扑排序

$\mathcal{B}$：P1137 旅行计划

给定一个 $n$ 个点，$m$ 条边的 DAG $G$ ，对于每一个点 $i\in[1,n]$ 求出以结点 $i$ 为终点的，只走一个方向的路径经过结点最多的数量。

思路：我们考虑如何求出结点 $i$ 的答案，注意到 $i$ 的答案取决于 $i$ 所有前驱的答案，发现这满足 拓扑性质。于是我们套用拓扑排序即可。时间复杂度 $\mathcal{O}(n+m)$。

代码：

void Toposort(){
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i++)
        if (!du[i]) q[++tt] = i;
    while (hh <= tt){
        int u = q[hh++];
        for (int i = h[u]; i; i = ne[i]){
            du[e[i]]--;
            f[e[i]] = max(f[e[i]],f[u]+1);
            if (!du[e[i]])
                q[++tt] = e[i];
        }
    }
    for (int i = 1; i <= n; i++)
        cout << f[i]+1 << endl;
}

$\mathcal{C}$：CF915D

给定一个 $n$ 个点，$m$ 条边的有向图 $G$ ，问是否可以删除一条边使其变成 DAG。

思路：如果我们 暴力枚举 删去的边并判断是否为 DAG，时间复杂度 $\mathcal{O}(m(n + m))$。我们可以换一个角度去考虑，删除一条边实际上是某一个点的入度 $-1$，于是可以枚举哪个点的入度 $-1$，时间复杂度 $\mathcal{O}(n(n + m))$。

namespace Star_F{
    const int N = 505, M = 100005;
    int n, m;
    int h[N], e[M], ne[M], idx;
    int du[N], t[N];
    void add(int u,int v){
        e[++idx] = v, ne[idx] = h[u], h[u] = idx;
    }
    bool topo(){
        int cnt=0;	
        queue<int> q;
        for (int i = 1; i <= n; i++)
            if(du[i]==0) q.push(i);
        while(!q.empty()){
            int u = q.front(); q.pop();	
            cnt++;
            for (int i = h[u]; i;i=ne[i]) 
                if(--du[e[i]]==0) q.push(e[i]);
        }
        return cnt == n;
    }
    void Main(){
        memset(h, 0, sizeof(h)), idx = 0;
        cin >> n >> m;
        for (int i = 1; i <= m;i++){
            int u, v; cin >> u >> v;
            add(u, v);
            du[v]++;
        }
        for (int i = 1; i <= n;i++) t[i] = du[i];
        for (int i = 1; i <= n;i++){
            du[i]--; 
            if(topo()){
                cout << "YES" << endl;
                return;
            }
            for (int i = 1; i <= n;i++) du[i] = t[i];
        }
        cout << "NO" << endl;
    }
}

由于拓扑排序不容易单独出题，于是考虑将一些难题放入 $\mathcal{Part \ 8}$ 图论综合部分。

$\mathcal{Part \ 3}$：最短路（Shortest Path）

$\mathcal{Part\ 3.1}$： 一些定义

带权图：有向图或无向图可以加上边权，边记为 $(u, v, w)$ 。边权值非负的图称为非负权图，边权为正的图称为正权图。

路径长度：带权图中路径上每条边的边权之和。用 $L(v_0 \to v_1 \to \dots \to v_k)$ 表示。

负环：边权和为负数的环。

最短路：最短的连接 $s$ 到 $t$ 的路径。若不存在这样的路径或最小值不存在，则最短路不存在。

$\mathcal{Part\ 3.2}$：单源最短路径问题

$\text{Problem}$：给定一个源点 $S$，求出 $S$ 到图上每个点 $u$ 的最短路径长度 $D_u$。

在下面的算法中，我们定义 $\text{dis}_u$ 表示 $S$ 到 $u$ 的估计最短距离，初始值：$\text{dis}_S =0 ,\text{dis}_u=+\infty(u\in [1,n],u\ne S)$。

算法结束时有 $\text{dis}_u=D_u(u\in[1,n])$。负环均指源点可达负环。

3.2.1：Bellman-Ford

核心思想是进行松弛操作，松弛表示对每条边 $(u, v, w)$，用 $\text{dis}_u + w$ 更新 $\text{dis}_v$，松弛 $n - 1$ 轮。

判断是否存在负环：松弛 $n$ 轮，若第 $n$ 轮还有 $\text{dis}_u$ 被更新，则一定存在负环。

证明：不妨归纳假设 $x$ 轮松弛可以得到所有最短路边数 $\leq x$ 的点的 $D_u$。显然 $x = 0$ 时正确（初始状态，无松弛，最短路边数为 $0$ ）。 不妨设 $x = k$ 时正确，考虑最短路边数为 $k + 1$ 的点。设其最短路径为 $s \to p_1 \to \dots \to p_k \to u$，由于 $\text{dis}_{p_k} = D_{p_k}$（归纳假设，$k$ 轮松弛已处理边数 $\leq k$ 的最短路径 ），因此一轮松弛（第 $k + 1$ 轮 ）后，$\text{dis}_u$ 会被更新为 $D_u$（通过边 $p_k \to u$ 的松弛操作 ）。

若不存在负环，所有点的最短路边数 $\leq n - 1$（$n$ 个顶点的图，最长简单路径边数为 $n - 1$ ），故 $n - 1$ 轮松弛后，所有点的最短路径都能被正确计算。

若存在负环，负环会导致路径长度可无限减小（每绕环一次，总长度更短 ）。此算法有限轮松弛只能处理“长度有限”的最短路径，而负环会让某些点的最短路径长度无限迭代更新，因此第 $n$ 轮若仍有更新，可判定存在负环。

时间复杂度：$\mathcal{O}(nm)$（$n$ 轮松弛，每轮遍历 $m$ 条边 ）。

代码如下：

int dis[N][N],n,m; //dis[k][v];表示选取前k个时到达i的最短距离
struct Edge{ int u, v, w;} edge[N];
void Bellman_Ford(int s){
    memset(dis, INF, sizeof(dis));
    for (int i = 1; i <= n; i++)  dis[i][s] = 0;
    for (int k = 1; k <= n - 1; k++)            
        for (int i = 0; i < m; i++){
            int u = edge[i].u, v = edge[i].v, w = edge[i].w;
            dis[k][v] = min(dis[k][v], dis[k - 1][u] + w);    //松弛操作
        }
}

3.2.2：SPFA

SPFA（Shortest Path Faster Algorithm）是队列优化的 Bellman-Ford。
当松弛某个点 $u$ 时，对于所有与 $u$ 相邻且 $\text{dis}_v$ 被更新的点 $v$，若 $v$ 当前不在队列中，则将其压入队列。每次从队列中取出一个点进行松弛操作。
为检测负环，每个点额外记录最短路当前经过的边数 $\text{cnt}_u$；若存在某个点 $u$ 使得 $\text{cnt}_u \geq n$，则判定图中存在负环。

实际上其松弛过程与 Bellman-Ford 类似，可感性理解为：队列中始终维护了 ”可能通过进一步松弛缩短路径” 的点集。每次取出队首点松弛其邻接边，相当于 Bellman-Ford 中 “按需” 进行的局部松弛，避免了对所有边进行冗余检查。

时间复杂度：最坏仍为 $\mathcal{O}(nm)$。在一般随机图上效率常优于 Bellman-Ford，但有特殊数据可以卡，需要慎重使用！

代码如下：

void SPFA(){
    for (int i = 1; i <= n; i++) dis[i] = INF, vis[i] = 0;
    dis[s] = 0, vis[s] = 1, Q.push(s);
    while (!Q.empty()){
        int u = Q.front(); Q.pop();
        vis[u] = 0;
        for (int i = h[u]; i; i = e[i].nxt){
            int v = e[i].to;
            if (dis[v] > dis[u] + e[i].c){     // 松弛操作
                dis[v] = dis[u] + e[i].c;
                if (!vis[v])
                    vis[v] = 1, Q.push(v);
            }
        }
    }
}

3.2.3：Dijkstra

Dijkstra 算法只适用于非负权图。

称 扩展 节点 $u$ 表示对 $u$ 所有的出边 $(u, v, w)$ 用 $\text{dis}_u + w$ 更新 $\text{dis}_v$。每次选择 $\text{dis}$ 最小的 未扩展过 的 $u$，对 $u$ 进行扩展。

证明：只需要证明每次扩展的 $u$ 满足 $\text{dis}_u = D_u$。不妨归纳假设已经扩展过的点 $p_1, …, p_{k-1}$ 满足 $\text{dis}_u = D_u$，考虑下一个扩展的 $p_k$ 一定也得到最短路。否则也就意味着存在更短的路径 $s \rightsquigarrow p_i \rightarrow u_1 \rightsquigarrow p_k$，其中 $u_1$ 是没有被扩展的点，则此时 $\text{dis}_{u_1} < \text{dis}_{p_k}$，与 $p_k$ 的选择矛盾。因此归纳成立。

稀疏图实现时使用优先队列，扩展时如果有更新，则把 $(v, \text{dis}_v)$ 加入优先队列。每次从优先队列中取出最小的没有被扩展过的进行扩展。注意判断 $(v, d)$ 中的 $d$ 是否等于 $\text{dis}_v$，若不等则已经被扩展过。时间复杂度 $O(m \log m)$。

稠密图每次暴力找最小值，时间复杂度 $O(n^2)$。

当边权只有 0 和 1 时，使用双端队列代替优先队列。称为 01 BFS。时间复杂度 $O(n + m)$。

代码如下：

// 优先队列版本
const int N = 200005;
int n, m, s, dis[N];
vector<PII> v[N];
bool vis[N];
struct node{
    int d, id;
    bool friend operator<(node x, node y){
        return x.d > y.d;
    }
};
priority_queue<node> Q;
void dij(){
    for (int i = 1; i <= n; i++) dis[i] = INF;
    dis[s] = 0;
    Q.push({0, s});
    while (!Q.empty()){
        int d = Q.top().d, id = Q.top().id;
        Q.pop();
        if (d > dis[id]) continue;
        if(vis[id]) continue;
        vis[id] = 1;
        for (int i = 0; i < v[id].size(); i++){
            int to = v[id][i].fi;
            if (dis[to] > dis[id] + v[id][i].se){
                dis[to] = dis[id] + v[id][i].se;
                Q.push({dis[to], to});
            }
        }
    }
}

3.2.4：总结

根据题目给出的数据范围，选择适合的算法。（如存在负环则不能使用 Dijkstra，稠密图和稀疏图等）。

$\mathcal{Part\ 3.3}$：全源最短路径问题

$\text{Problem}$：求出任意两点之间的最短距离 $D_{s,t}$。

3.3.1：Johnson

新建一个超级源点 $0$，从超级源点 0 向所有点连边，跑 BF/SPFA 得到最短路 $h_u$。将边 $(u, v, w)$ 改为 $(u, v, w + h_u - h_v)$，在新图上以 $s$ 源点跑 Dijkstra，则 $D_{s,t} = D_t + h_t - h_s$。

证明：考虑对边进行操作后，原图和新图上路径长度

$$L(s \rightarrow u_1 \rightarrow \cdots \rightarrow u_{k-1} \rightarrow t) = w_1 + w_2 + \cdots + w_k \\ L'(s \rightarrow u_1 \rightarrow \cdots \rightarrow u_{k-1} \rightarrow t) = w_1 + h_s - h_{u_1} + w_2 + h_{u_1} - h_{u_2} + \cdots + w_k + h_{u_{k-1}} - h_t \\ = L(s \rightarrow u_1 \rightarrow \cdots \rightarrow u_{k-1} \rightarrow t) + h_s - h_t$$

只相差一个只与起点终点有关的数，因此原图的最短路在新图上也是最短路。再考虑 $h$ 是最短路，因此 $h_v \leq h_u + w$，也就是新图是非负权图，可以使用 Dijkstra。

时间复杂度 $O(nm \log m)$。

代码如下：

namespace Star_F {
    const int N = 5005, M = N << 1;
    struct edge {
        int v, w, nxt;
    } e[M];
    struct node {
        int dis, id;
        bool operator<(const node& a) const { return dis > a.dis; }
        node(int d, int x) { dis = d, id = x; }
    };
    const int INF = 1e9;
    int head[N], vis[N], t[N], cnt, n, m;
    ll h[N], dis[N];
    void add(int u, int v, int w) {
        e[++cnt].v = v, e[cnt].w = w, e[cnt].nxt = head[u], head[u] = cnt;
    }
    bool spfa(int s) {
        queue<int> q;
        memset(h, 63, sizeof(h));
        h[s] = 0, vis[s] = 1;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();q.pop();
            vis[u] = 0;
            for (int i = head[u]; i; i = e[i].nxt) {
                int v = e[i].v;
                if (h[v] > h[u] + e[i].w) {
                    h[v] = h[u] + e[i].w;
                    if (!vis[v]) {
                        vis[v] = 1;
                        q.push(v); t[v]++;
                        if (t[v] == n + 1) return false;
                    }
                }
            }
        }
        return true;
    }
    void dijkstra(int s) {
        priority_queue<node> q;
        for (int i = 1; i <= n; i++) dis[i] = INF;
        memset(vis, 0, sizeof(vis));
        dis[s] = 0;
        q.push(node(0, s));
        while (!q.empty()) {
            int u = q.top().id; q.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            for (int i = head[u]; i; i = e[i].nxt) {
                int v = e[i].v;
                if (dis[v] > dis[u] + e[i].w) {
                    dis[v] = dis[u] + e[i].w;
                    if (!vis[v]) q.push(node(dis[v], v));
                }
            }
        }
    }
    void Main() {
        n = rd(); m = rd();
        for (int i = 1; i <= m; i++) {
            int u = rd(), v = rd(), w = rd();
            add(u, v, w);
        }
        for (int i = 1; i <= n; i++) add(0, i, 0);
        if (!spfa(0)) {
            cout << -1 << endl;
            return;
        }
        for (int u = 1; u <= n; u++)
            for (int i = head[u]; i; i = e[i].nxt) e[i].w += h[u] - h[e[i].v];
        for (int i = 1; i <= n; i++) {
            dijkstra(i);
            long long ans = 0;
            for (int j = 1; j <= n; j++) {
                if (dis[j] == INF)
                    ans += j * INF;
                else
                    ans += j * (dis[j] + h[j] - h[i]);
            }
            cout << ans << endl;
        }
    }
}

3.3.2：Floyd（传递闭包）

初始化所有 $\text{dis}_{u,u} = 0, (u, v, w) \in E, \text{dis}_{u,v} \leftarrow w$。枚举中转点 $k$，起点 $i$，终点 $j$，用 $\text{dis}_{i,k} + \text{dis}_{k,j}$ 更新 $\text{dis}_{i,j}$。注意中转点必须在最外层枚举。

考虑这样一个算法，$\text{dis}_{k,s,t}$ 表示 $s \leftrightarrow t$ 只经过编号 $\leq k$ 的最短路（不包括起点终点），转移即为加入 $k+1$，也就是 $\text{dis}_{k+1,s,t} = \min(\text{dis}_{k,s,t}, \text{dis}_{k,s,k+1} + \text{dis}_{k,k+1,t})$。

事实上省略第一维导致的重复转移并不会影响答案，即得到正常写的 Floyd 算法。

时间复杂度 $O(n^3)$。

此外 Floyd 计算闭包，也就是两点可达性可以做到 $O\left(\frac{n^3}{\omega}\right)$。$\omega$ 为 bitset 提供的 $\frac{1}{64}$ 常数优化。

代码如下：

for (k = 1; k <= n; k++)
    for (i = 1; i <= n; i++)
        for (j = 1; j <= n; j++)
            dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

3.3.3：总结

还是要根据不同的数据来使用不同的算法，Floyd 优势在于代码简洁，如果图为稠密图，即 $m\approx n^2$ 时，选择 Floyd 算法更优。

$\mathcal{Part\ 3.4}$：扩展问题

3.4.1：最短路树（SPT）

我们希望用一个树形结构去刻画 $s$ 到每个点的最短路。在单源最短路径中，记录每个点最后被更新的前驱 $f_i$，即可得到图的最短路树。

不难发现一定满足 $\text{dis}_{f_i} + w(f_i, i) = \text{dis}_i$，并且一定不会存在环，也就是从 $s$ 出发沿树上走简单路径得到的就是最短路。

类似也能得到到达 $s$ 的最短路树。

扩展：在不含零环的图上保留 $\text{dis}_u + w = \text{dis}_v$ 的边，得到有向无环图（若有环则必然是零环）称为最短路 DAG。此 DAG 任意路径都是最短路，任意最短路在 DAG 上，任意生成树都是最短路树。

例：CF545E Paths and Trees

无向正权联通图，求从 $u$ 出发权值和最小的最短路树。

我们定义 $\text{pre}_i$ 表示最短路树上点 $i$ 的前驱，由于建的图是双向边，所以输出 $\lceil \frac{\text{pre}_i}{2} \rceil$ 即可。

代码如下：

namespace Star_F{
    const int N = 3e5 + 10, M = N << 1, inf = 0x7f;
    int n, m, s, h[N], e[M], ne[M], w[M], idx, pre[N];
    ll dis[N];
    bool vis[N];
    struct node{
        int to;
        ll w;
        bool operator<(const node &a) const{
            return w > a.w;
        }
    };
    priority_queue<node>q;
    void add(int a,int b,int c){
        e[++idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx;
    }
    void dij(){
        memset(dis, inf, sizeof dis);
        q.push((node){s, 0});
        dis[s] = 0;
        while(!q.empty()){
            int u=q.top().to;q.pop();
            if(vis[u]) continue;
            vis[u] = 1;
            for (int i = h[u]; i; i = ne[i]){
                int v = e[i];
                if (dis[v] >= dis[u] + w[i]){
                    dis[v] = dis[u] + w[i];
                    q.push((node){v, dis[v]});
                    pre[v] = i;
                }
            }
        }
    }
    void Main(){
        n = rd, m = rd;
        for (int i = 1; i <= m; i++){
            int a = rd, b = rd, c = rd;
            add(a, b, c), add(b, a, c);
        }
        s = rd;
        dij();
        ll sum = 0;
        for (int i = 1; i <= n; i++){
            if (i == s) continue;
            sum += w[pre[i]];
        }
        cout << sum << endl;
        for (int i = 1; i <= n; i++)
            if (i != s) cout << (pre[i] + 1 >> 1) << " ";
    }	
}

3.4.2：删边最短路

$\text{Problem}$：给定正权无向图，求删除每一条边后 1 到 n 的最短路。

定义从 1 出发的最短路树为 $T_1$，达到 $n$ 的最短路树为 $T_n$。我们用 $T(y)$ 表示树 $T$ 上到 $y$ 的路径。

对于边 $(i, j)$ 若不在原最短路上则最短路不变，否则不妨设原最短路是 $1 \rightsquigarrow i \to j \rightsquigarrow n$，找到边 $(u, v, w)$ 使得 $u$ 不在 $T_1$ 中 $j$ 的子树内，$v$ 不在 $T_n$ 中 $i$ 的子树内。也就是只经过一条非树边。

具体实现时枚举非树边 $(u, v, w)$，找到 $u’ = \text{LCA}_{T_1}(u, n), v’ = \text{LCA}_{T_n}(v, 1)$，对于最短路 $(u’, v’)$ 之间的边用 $L(T_1(u)) + w + L(T_n(v))$ 更新答案。使用线段树等数据结构可做到 $O(m \log m)$。

证明：以下的证明中认为 $T_1$ 中到 $n$ 的路径和 $T_n$ 中到 $1$ 的路径相同。

不妨设 $T_1$ 上 $j$ 的子树为 $A_j$，子树外为 $A_i$，$T_n$ 上 $i$ 的子树为 $B_i$，子树外为 $B_j$。

先证明 $A_j \cap B_i = \emptyset$，考虑若 $u \in A_j \cap B_i$，考虑下图

其中 $a$ 为 $i \leftrightarrow j$ 边权，$c$ 为 $j \rightsquigarrow u$ 的最短路，$b$ 为 $i \rightsquigarrow u$ 的最短路，由于 $u \in A_j$，因此 $L(1 \rightsquigarrow i) + a + c \leq L(1 \rightsquigarrow i) + b$，即 $a + c \leq b$，同理 $a + b \leq c$，两式相加得到 $a \leq 0$ 矛盾。

于是考虑删边后的最短路 $P’$，由于 $1 \in A_i, n \in A_j$，找到第一条 $(u, v, w)$ 满足 $u \in A_i, v \in A_j$，把 $1 \rightsquigarrow u$ 换成 $T_1(u)$，不会经过 $(i, j)$，由于是最短路显然不劣，再由于之前的证明 $v \notin B_i$ 即 $v \in B_j$，同理可以替换成 $T_n(v)$，这样就得到只相差一条非树边的最短路。

例：P2685 [TJOI2012] 桥

3.4.3：平面图最小割

我们先考虑网格图的最小割，事实上和一般平面图没有本质区别。

网格图从左上角 $s$ 到右下角 $t$ 的最小割，找到一种划分点集的方式 $V = S \cup T$ 满足 $s \in S, t \in T$ 且两端分别在 $S$ 和 $T$ 的边（即割边）权值之和最小。

考虑起点和终点把图外的平面分为两部分。我们把所有面建一个点，原来的边在边两边的平面对应的点连边，得到平面图的对偶图。

显然对偶图的最短路可以对应到一个合法的割。同样对于一个合法的割，对偶图中必然存在一条从左下到右上的路径。

也就是 平面图最小割等于对偶图最短路。

例：P4001 [ICPC-Beijing 200] 狼抓兔子

$\mathcal{Part\ 3.5}$：例题详解

$\mathcal{A}$：P1144 最短路计数

求出从顶点 $1$ 开始到每个点的最短路径的方案数。

思路：其实就是板子题，在每次更新最短路的时候，顺便记录一下方案数就可以。另外由于本题的边权都是 $1$，所以无需使用堆优化，使用普通的队列即可。

代码如下：

queue<int> Q;
d[1] = 0, vis[1] = 1, c[1] = 1;
Q.push(1);
while (!Q.empty()){
    int x = Q.front();
    Q.pop();
    for (int i = 0; i < G[x].size(); i++){
        int t = G[x][i];
        if (!vis[t]){
            vis[t] = 1;
            d[t] = d[x] + 1;
            Q.push(t);
        }
        if (d[t] == d[x] + 1)      // 顺便记录方案数
            c[t] = (c[t] + c[x]) % MOD;
    }
}

$\mathcal{B}$：P1462 通往奥格瑞玛的道路

$n$ 个点，$m$ 条边的无向图，边有边权，点有点权，求出一条 $1$ 到 $n$ 的路径，使得 边权之和 小于给定限制 $b$，并且最小化经过点权的最大值。$1 \le n\le10^4,1\le m \le 5\times10^4$。

思路：看到求最大值最小，我们考虑二分答案。二分一个最大点权 $\text{mid}$，如果我们可以找到一条 只走点权 $\le \text{mid}$ 的点，并且边权和 $\le b$ 的一条路径 那么我们，那么我们更新 $l$ ，否则更新 $r$。时间复杂度 $\mathcal{O}(m\log m\log \max_{i=1}^{f_i})$。可以通过。

代码如下：

namespace Star_F{
    const int N = 10005, M = 100005, INF = 0x3f3f3f3f;
    int h[N], ne[M], e[M], w[M], idx;
    int n, m, k, a[N], l = INF, r, flag;
    void add(int u,int v,int W){
        e[++idx] = v, ne[idx] = h[u], w[idx] = W, h[u] = idx;
    }
    int dis[N];
    priority_queue<PII> q;
    bool check(int mid){
        memset(dis, -1, sizeof(dis));
        dis[1] = k;
        q.push({dis[1], 1});
        while(!q.empty()){
            int u = q.top().se, d = q.top().fi;
            q.pop();
            if(dis[u]!=d) continue;
            for (int i = h[u]; i;i=ne[i]){
                int v = e[i];
                if(a[v]>mid) continue;
                if(dis[v]<dis[u]-w[i]&&dis[u]-w[i]>=0){
                    dis[v] = dis[u] - w[i];
                    q.push({dis[v], v});
                }
            }
        }
        return dis[n] != -1;
    }
    void Main(){
        cin >> n >> m >> k;
        for (int i = 1; i <= n;i++){
            cin >> a[i];
            l = min(l, a[i]), r = max(r, a[i]);
        }
        flag = r;
        for (int i = 1; i <= m;i++){
            int u, v, w;
            cin >> u >> v >> w;
            add(u, v, w), add(v, u, w);
        }
        l = a[1];
        while(l<=r){
            int mid = l + r >> 1;
            if(check(mid)) r = mid - 1;
            else l = mid + 1;
        }
        if(l==flag+1) cout << "AFK" << endl;
        else cout << l << endl;
    }
}

$\mathcal{C}$：P4568 [JLOI2011] 飞行路线

给定一个 $n$ 个点，$m$ 条边的无向图，有边权，其中可以将 $k$ 条边的边权变为 $0$ ，求 $s\to t$ 的最短路径。

思路：分层图模板题目。

我们考虑给每一层的内部正常连边，每层之间从上到下连权值为 $0$ 的边。如果我们这样建图的话，相当于每向下走一层，就相当于使用一次边权变为 $0$，所以我们求 $s$ 到 $t+n\times k$ 的最短路即可。(多加了 $k$ 层，每层 $n$ 个结点，所以是 $t+n\times k$ )。

但是我们发现，其实可以不把分层图真的建出来，而是在求最短路的时候，使用动态规划的思想更新答案。

具体来讲，我们定义 $dis_{i,j}$ 表示从 $s$ 到 $i$ ，使用了 $j$ 次边权变为 $0$ 的最短路径长度。

对于一条边 $(u,v,w)$ 转移如下：

$$\text{dis}_{v,j}= \begin{cases} \min(\text{dis}_{v,j},\text{dis}_{u,j-1}) \ \ (j\le k) \\ \\ \min(\text{dis}_{v,j},\text{dis}_{u,j}+w) \end{cases}$$

时间复杂度：$\mathcal{O}(k\times m\log m)$。

代码如下：

void Dijkstra(){
    memset(vis, 0, sizeof vis), memset(dis, 0x3f, sizeof dis);
    dis[s][0] = 0;
    priority_queue<node> q;
    q.push({0, 0, s});
    while (!q.empty()){
        int l = q.top().pos, cnt = q.top().cnt;
        q.pop();
        if (vis[l][cnt])continue;
        vis[l][cnt] = 1;
        for (int i = head[l]; i; i = e[i].next){
            int r = e[i].to, w = e[i].w;
            if (cnt < k and dis[r][cnt + 1] > dis[l][cnt]){
                dis[r][cnt + 1] = dis[l][cnt];
                q.push({dis[r][cnt + 1], cnt + 1, r});
            }
            if (dis[r][cnt] > dis[l][cnt] + w){
                dis[r][cnt] = dis[l][cnt] + w;
                q.push({dis[r][cnt], cnt, r});
            }
        }
    }
    int ans = 0x3f3f3f3f;
    for (int i = 0; i <= k; i++)
        ans = min(ans, dis[t][i]);
    cout << ans << endl;
}

$\mathcal{Part \ 4}$：双连通分量

$\mathcal{Part\ 4.1}$：一些定义

• 割点：删去后使连通分量增加的点。

• 割边：删去后使连通分量增加的边，也称桥。

• 点双连通图：不存在割点的无向连通图。

• 边双连通图：不存在割边的无向连通图。

• 点双连通分量：极大点双连通子图，简称点双（V-BCC）。

• 边双连通分量：极大边双连通子图，简称边双（E-BCC）。

• 点双连通：$u, v$ 处于同一个点双。

• 边双连通：$u, v$ 处于同一个边双。

$\mathcal{Part\ 4.2}$：无向图 DFS 树

给定无向连通图 $G$，从 $r$ 开始 DFS，取出进入每个点 $i$ 时对应的边 $(\text{fa}_i, i)$ 得到以 $r$ 为根的叶向树。称 $(\text{fa}_i, i)$ 为树边，其余边为非树边。

每个点标号为被访问到的次序称为时间戳，简称 $\text{dfn}$。

最重要的性质是非树边两端具有 祖先后代关系。

$\mathcal{Part\ 4.3}$：双连通的简单性质

4.3.1：边双连通

直观理解边双：每断开一条割边，连通块个数都会加一。如果断开所有割边，会得到割边条数 $+1$ 个联通分量，每个联通分量都是边双。如果把同一个边双内的点进行缩点，得到一棵树。

下面的结论是显然的：

称从 $u$ 到 $v$ 必须经过的边为必经边，那么：

1. 两点之间任意一条迹上的所有割边，就是两点之间的所有必经边。

2. $a$ 和 $b$ 边双连通，$b$ 和 $c$ 边双连通，则 $a$ 和 $c$ 边双连通。

3. $u, v$ 边双连通当且仅当 $u, v$ 之间没有必经边。

对于一条边 $(u, v)$，删去后找到路径 $u \rightsquigarrow v$，拼起来就是回路。

1. 边双内任意一条边 $(u, v)$ 存在经过此边的回路。

2. 边双内任意一点 $u$ 存在经过此点的回路。

3. 边双内任意两点 $u, v$，存在经过两点的回路。

4.3.2：点双联通

直观理解点双：两个点双最多只有一个交点，不然就会变成一个。若 $S_1$ 与 $S_2$、$S_2$ 与 $S_3$ 有交，$S_3$ 与 $S_1$ 有交，那么交点一定是同一个。于是所有点双会形成类似树形的结构。

下面的结论是显然的：

1. 若两点双有交，那么交点一定是割点。

2. 一个点是割点当且仅当它属于超过一个点双。

3. 一条边直接连接的两点点双连通。

4. 一条边恰属于一个点双。

对于 $n \geq 3$ 的点双，对于点 $x$，度数必然 $\geq 2$，删去后找到相邻的 $u, v$，找到一条 $u, v$ 的路径拼起来。

1. $n \geq 3$ 的点双内任意一点 $u$ 存在经过此点的简单环。

2. 点双内任意两点 $u, v$，存在经过这两点的简单环。

我们也可以得到更多的推论：

1. $n \geq 3$ 的点双内对于点 $x$ 和边 $e$，存在经过 $x$ 和 $e$ 的简单环。

证明：把 $e = (u, v)$ 拆成 $(u, w), (w, v)$，显然不影响点双连通性，找经过 $x, w$ 的简单环即可。

1. $n \geq 3$ 的点双内对于点 $x \neq y$ 和边 $e$ 存在 $x \rightsquigarrow e \rightsquigarrow y$ 的简单路径。

证明：找经过 $x, e$ 的简单环 $C$，若 $y \in C$ 则成立。否则找到任意 $y \rightsquigarrow x$ 的路径 $P$，找到第一个 $C$ 上的点 $z$，必然存在 $z \neq x$ 的 $P$，拼接环 $C$ 的部分和 $z \rightsquigarrow y$ 的部分即可。

1. $n \geq 3$ 的点双任意不同三点 $x, y, z$ 存在 $x \rightsquigarrow y \rightsquigarrow z$ 的路径。

$\mathcal{Part\ 4.4}$：点双

$\mathcal{Part\ 4.5}$：边双

$\mathcal{Part\ 4.6}$：圆方树

$\mathcal{Part \ 5}$：强连通分量

$\mathcal{Part\ 5.1}$：一些定义

$\mathcal{Part\ 5.2}$：有向图 DFS 树

$\mathcal{Part\ 5.3}$：SCC

$\mathcal{Part \ 6}$：最小生成树

$\mathcal{Part\ 6.1}$：一些定义

$\mathcal{Part\ 6.2}$：最小生成树求法

$\mathcal{Part\ 6.3}$：Kruskal 重构树

$\mathcal{Part \ 7}$：拟阵

$\mathcal{Part\ 7.1}$：引入

$\mathcal{Part\ 7.2}$：拟阵上的最优化

$\mathcal{Part\ 7.3}$：拟阵交

$\mathcal{Part \ 8}$：图论综合

---

到此为止，图论相关入门算法已全部介绍完毕。

欢迎反馈错误，欢迎私信交流。

$图论入门：\text{Finished}$。 $图论进阶：\text{Will Come!}$