CSP暑期集训 Day03 - 最短路与欧拉路

DAY 03

最短路与欧拉路

CSP 暑期集训 · Shortest Path & Euler Path

🛤️

Dijkstra

单源最短路（贪心+优先队列）

🌐

Floyd-Warshall

全源最短路（DP三重循环）

🔔

Bellman-Ford / SPFA

负权边最短路·队列优化

🔄

欧拉路/回路

一笔画问题·Hierholzer算法

✏️ 📎

🎯 单源最短路问题（Single Source Shortest Path, SSSP）
给定带权图 G=(V,E) 和起点 s，求 s 到所有其他顶点的最短距离。
前提：所有边权 ≥ 0（Dijkstra 不能处理负权边！负权边需用 SPFA/Bellman-Ford）

📌 为什么不能暴力搜索？

暴力法的复杂度分析：
DFS/BFS 枚举所有路径取最短。设图中有 n 个节点、m 条边。
从 s 出发，每步有 O(n) 种选择，路径长度可达 O(n)。

总路径数 ≈ O(n!)，指数级复杂度，完全不可行

即使只枚举简单路径（无环），数量仍可达 O(2ⁿ)。
需要更聪明的策略！

💡 Dijkstra 的贪心策略 — 核心思想

⚡ 核心：每次从未确定的节点中，选 dist 最小的节点 u —— 它的最短路已经确定！
然后从 u 出发，松弛（relax）所有邻居的 dist 值。重复 n 次即完成。

📐 贪心正确性证明（反证法）：
① 设已确定集合 S，未确定集合 V-S。当前未确定节点中 dist 最小的是 u。
即 dist[u] = min{dist[v] | v ∈ V-S}
② 假设：u 的最短路不是 dist[u]，存在更短路径 P，且 P 经过某个未确定节点 w。
③ 路径 P 在到达 u 之前必须先到达 w，因此：
len(P) = dist[s→w] + len[w→...→u] ≥ dist[w]（因为边权 ≥ 0）
④ 但 u 是 dist 最小的未确定节点，所以 dist[u] ≤ dist[w]
⑤ 综合③④：len(P) ≥ dist[w] ≥ dist[u]，与假设 len(P) < dist[u] 矛盾！
⑥ ∴ 假设不成立，dist[u] 就是 u 的最终最短路 ✅

📋 样例数据

4个节点，5条有向边，起点 s=1
1 → 2，权=2 | 1 → 3，权=7 | 1 → 4，权=5
2 → 3，权=3 | 2 → 4，权=1 | 4 → 3，权=1
目标：求节点1到所有节点的最短距离

🖼️ 样例图（含全部5条边）

📊 dist 数组逐步确定

⚠️ 为什么 Dijkstra 不能处理负权边？

贪心策略的局限性：
Dijkstra 的核心是：一旦节点 u 被标记为"已确定"，就不再更新。
这个策略依赖的前提是：后续路径只会让距离更大（因为边权 ≥ 0）。
但如果有负权边，后续路径可能让距离更小！已确定的值就可能是错的。

📐 反例构造（3节点图）

边：1→2 权=1，1→3 权=3，3→2 权=-5

Dijkstra 执行过程（从节点1出发）：
① dist=[0, ∞, ∞]，选节点1（dist=0），松弛邻居：
   dist[2] = min(∞, 0+1) = 1
   dist[3] = min(∞, 0+3) = 3
② dist=[0, 1, 3]，选节点2（dist=1，最小），标记为已确定 ✓
   节点2无出边，无法松弛
③ dist=[0, 1, 3]，选节点3（dist=3），松弛 3→2：
   dist[2] = min(1, 3+(-5)) = min(1, -2) = -2，但节点2已确定！不再更新！

⚡ 错误结果

Dijkstra 输出 dist[2] = 1，但实际最短路径是 1→3→2 = 3+(-5) = -2！
贪心策略在负权边下彻底失效！

💡 生活类比：想象你在导航软件中查路线——Dijkstra 就像「每次都先确认离你最近的未访问路口」，这保证了每一步都在扩展最短的可能性。

📐 松弛操作（Relaxation）的数学定义

定义：对于边 (u, v) 权值为 w，检查是否可以通过 u 来缩短 s 到 v 的距离：

若 dist[v] > dist[u] + w(u,v)，则令 dist[v] = dist[u] + w(u,v)

直觉：「经过 u 中转到达 v，比当前已知路径更短吗？」
类比：你本来走直路到家要 10 分钟，但经过朋友家绕一下只要 7 分钟 → 更新路线！

🖼️ SVG图解：松弛操作逐步演示

🔍 松弛失败的情况

反例：dist[u]=3, dist[v]=4, w(u,v)=5

dist[u] + w = 3 + 5 = 8 > dist[v] = 4 → 不更新！

直走更短，经过 u 中转反而更远。松弛失败，dist[v] 保持 4。

⚠️ 易错点：
① 松弛操作必须用已确定的节点 u 去松弛邻居 v。如果 u 本身的 dist 还可能被更新，那么用它松弛出来的 dist[v] 也可能不是最终值。
② 这就是为什么 Dijkstra 每次必须选 dist 最小（已确定最优）的节点来执行松弛。
③ 每条边最多被松弛一次——这个性质在分析复杂度时很重要！

💡 一句话总结松弛：「我能通过你走到目标更近吗？能就更新，不能就保持原样。」

📊 朴素版 vs 优先队列优化版对比

对比项	朴素Dijkstra	优先队列优化
找最小dist	遍历所有节点 O(n)	堆顶 O(1)
松弛后更新	直接改数组 O(1)	插入堆中 O(log n)
总找最小次数	n次 × O(n) = O(n²)	n次 × O(1) = O(n)
总松弛更新次数	O(1) × m = O(m)	O(log n) × m = O(m log n)
总复杂度	O(n² + m) = O(n²)	O((n+m) log n)
适用场景	稠密图（m ≈ n²）	稀疏图（m ≈ n）

📈 复杂度数学推导

优先队列优化版复杂度推导（逐步分析）：
① 初始化 dist 数组：遍历 n 个节点 → O(n)
② 起点入堆：1次堆插入 → O(log n)
③ 主循环：每个节点最多被弹出 1 次（确定后不再处理），每次弹出 O(log n)
但注意：松弛时会产生「旧副本」入堆，总入堆次数 ≤ n + m（n个节点 + m次松弛）
弹出总次数 ≤ n + m，每次 O(log n) → O((n+m) log n)
④ 松弛操作本身：每条边最多触发 1 次，每次 O(1) → O(m)
⑤ 总和 = O(n) + O((n+m) log n) + O(m) = O((n+m) log n)

稀疏图 m = O(n)：O(n log n) 远优于 O(n²)

稠密图 m = O(n²)：O(n² log n) 反而不如朴素 O(n²)！

🖼️ SVG图解：优先队列操作过程

⚠️ 易错点 — 堆中旧值处理：
同一个节点可能在堆中出现多次（因为 dist 被多次更新）。解决方案：
懒删除：弹出 (d, u) 时，若 d > dist[u]，说明这是旧副本，直接跳过。这是最常用也最简单的做法。
精确删除：用 decrease-key 操作直接修改堆中值（需手写堆或 Fibonacci 堆），竞赛中不常用。

📝 洛谷 P4779【模板】单源最短路径（标准版）
给定 n 个点 m 条边的有向带权图，求从起点 s 到所有点的最短路。数据保证边权非负。
数据范围：n ≤ 10⁵, m ≤ 2×10⁵

#include <bits/stdc++.h>
using namespace std;

// ========== 常量定义 ==========
typedef pair<int,int> pii;          // (距离, 节点编号)，用于优先队列排序
const int N = 100005;                  // 最大节点数
const int INF = 0x3f3f3f3f;             // 无穷大（约10^9，避免加法溢出）

// ========== 全局变量 ==========
int n, m, s;                            // 节点数、边数、起点
vector<pii> adj[N];                    // 邻接表: adj[u] = {(v, w), ...}
int dist[N];                             // dist[u] = s到u的当前已知最短距离
bool vis[N];                             // vis[u] = u的最短路是否已确定

// ========== Dijkstra 核心函数 ==========
void dijkstra(int s) {
    // 第1步：初始化所有距离为无穷大
    memset(dist, 0x3f, sizeof(dist));   // 每个字节设为0x3f → 每int为0x3f3f3f3f
    dist[s] = 0;                          // 起点到自身距离为0

    // 第2步：建立小根堆（优先队列）
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    // greater使pair按第一维(距离)升序排列 → 堆顶是最小距离
    pq.push({0, s});                     // 起点入堆：距离0，节点s

    // 第3步：主循环 — 每次取dist最小的未确定节点
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop(); // 取堆顶（当前dist最小的节点）
        if (vis[u]) continue;             // 懒删除：已确定的旧副本，跳过
        vis[u] = true;                    // 标记u的最短路已确定

        // 第4步：松弛 — 用u去更新所有邻居v的距离
        for (auto& [v, w] : adj[u]) {     // 遍历u的每条出边 (u→v, 权w)
            if (dist[v] > dist[u] + w) {   // 松弛条件：经u到v更短？
                dist[v] = dist[u] + w;     // 更新v的最短距离
                pq.push({dist[v], v});      // 新距离入堆（旧副本会被懒删除）
            }
        }
    }
}

// ========== 主函数 ==========
int main() {
    scanf("%d%d%d", &n, &m, &s);         // 读入节点数、边数、起点
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);     // 读入一条有向边 u→v 权w
        adj[u].push_back({v, w});          // 加入邻接表
    }
    dijkstra(s);                           // 执行Dijkstra
    for (int i = 1; i <= n; i++)
        printf("%d ", dist[i]);             // 输出s到每个点的最短距离
    return 0;
}

💡 代码要点： ① pair第一维是距离（用于堆排序），第二维是节点编号； ② greater<pii> 实现小根堆（默认是大根堆）； ③ 懒删除避免修改堆中旧值，空间换时间； ④ 0x3f3f3f3f ≈ 10⁹，两个相加不会溢出 int（最大 2×10⁹ < 2.1×10⁹）

📝 P4779 样例输入：n=4, m=6, s=1
边：1→2(2), 2→3(2), 2→4(1), 1→3(5), 3→4(3), 1→4(4)
样例输出：0 2 4 3

️ SVG图解：样例图结构（P4779）

📊 逐步执行过程（5步完成，输出 0 2 4 3 = P4779 样例）

⚠️ 模拟过程易错点：
① 步骤②中 dist[3] 从 5→4，dist[4] 从 4→3 ——节点2的两条出边同时更新！ 2→4(1) 这条权值最小的边是关键
② 步骤③先弹出 dist=3 的节点4（不是节点3！），因为堆顶取最小值——这就是 Dijkstra 贪心的体现
③ 步骤⑤中弹出的 (5,3) 是步骤①产生的旧副本，d=5 > dist[3]=4，必须跳过（懒删除）

🎯 为什么需要 Bellman-Ford？
Dijkstra 的贪心策略无法处理负权边。我们需要一种不依赖贪心的算法——
Bellman-Ford 的核心思想极其暴力：对所有边进行 n-1 轮松弛，保证找到所有最短路。

💡 核心原理

📐 关键定理

在 n 个节点的图中，任意两点间的最短路最多经过 n-1 条边（否则一定有环，去掉环更短或相等）。

算法思想：
① 第 1 轮松弛后：所有"经过 ≤1 条边"的最短路被找到
② 第 2 轮松弛后：所有"经过 ≤2 条边"的最短路被找到
③ ...
④ 第 n-1 轮后：所有"经过 ≤n-1 条边"的最短路被找到 → 全部最短路确定！

📐 为什么能处理负权边？

Bellman-Ford 不依赖"已确定"的概念！
每一轮都无差别地检查所有边，不管之前的结果如何。
即使某个节点的 dist 被负权边"拉低"，下一轮松弛仍然可以继续使用它。
暴力枚举所有可能 → 不会错过任何更短路径！

🖼️ SVG图解：松弛轮次演示

时间：O(n × m)

空间：O(n + m)

负权边：✅ 支持

💡 优化小技巧：如果某一轮松弛没有任何 dist 被更新，说明已经收敛，可以提前结束！
这在实际中大大减少运行时间（很多图不需要 n-1 轮就能收敛）。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

// 边结构体：存储一条有向边
struct Edge {
    int u, v, w;  // 起点、终点、权值
};

int n, m, s;             // n节点, m边, s起点
vector<Edge> edges;      // 存所有边
int dist[10005];          // dist[i] = s到i的最短距离

// ========== Bellman-Ford 核心 ==========
bool bellman_ford() {
    // 初始化：起点距离为0，其余为无穷大
    for (int i = 1; i <= n; i++) dist[i] = INF;
    dist[s] = 0;

    // 进行 n-1 轮松弛
    for (int i = 1; i <= n - 1; i++) {
        bool updated = false;  // 标记本轮是否有更新
        for (int j = 0; j < m; j++) {  // 遍历所有边
            int u = edges[j].u, v = edges[j].v, w = edges[j].w;
            if (dist[u] != INF && dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;  // 松弛成功！
                updated = true;
            }
        }
        if (!updated) break;  // 优化：无更新则提前结束
    }

    // 第 n 轮检查负环：如果还能松弛，说明有负环
    for (int j = 0; j < m; j++) {
        int u = edges[j].u, v = edges[j].v, w = edges[j].w;
        if (dist[u] != INF && dist[v] > dist[u] + w)
            return false;  // 存在负环！
    }
    return true;  // 无负环，成功求出最短路
}

// ========== 主函数 ==========
int main() {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        edges.push_back({u, v, w});  // 存储边
    }
    if (bellman_ford()) {
        for (int i = 1; i <= n; i++)
            printf("%d ", dist[i] == INF ? 2147483647 : dist[i]);
    } else {
        printf("存在负环！\n");
    }
}

📐 复杂度分析

时间复杂度推导

外层循环：最多 n-1 轮（可提前结束）
内层循环：每轮遍历全部 m 条边

T(n,m) = (n-1) × m = O(n × m)

负环检测：额外 O(m)
总时间：O(n × m)

空间复杂度

边数组 O(m) + dist 数组 O(n) = O(n + m)

✅ 优点：
① 能处理负权边
② 能检测负环
③ 代码简单，不易出错

❌ 缺点：
① 复杂度 O(nm) 太高！
② n=10⁵, m=10⁵ → 10¹⁰ 次运算，超时
③ 需要更高效的算法 → SPFA

🎯 为什么要引入 SPFA？
Bellman-Ford 每轮盲目遍历所有边，但很多边根本不可能产生松弛。
核心观察：只有上一轮 dist 被更新的节点，它的出边才可能产生新的松弛！
SPFA = Shortest Path Faster Algorithm，用队列只处理"有变化的节点"。

💡 核心思想

⚡ SPFA = 队列优化的 Bellman-Ford
① 用一个队列维护"dist 被更新过的节点"
② 每次从队列取出一个节点 u，松弛它的所有出边
③ 如果邻居 v 的 dist 被更新，且 v 不在队列中 → 将 v 入队
④ 重复直到队列为空

📊 SPFA vs Bellman-Ford 对比

📐 复杂度分析

最好情况（稀疏图）

每个节点入队1次，每条边被检查1次 → O(m)

最坏情况

每个节点可能被多次入队（被反复松弛）
极端情况：每个节点入队 n 次 → O(n × m)（退化为 Bellman-Ford）

平均情况

对于随机图，SPFA 通常接近 O(m)，非常快！

⚠️ SPFA 被卡常的风险！
某些竞赛题目会专门构造数据让 SPFA 退化为 O(nm)。
应对策略：① 边权非负时用 Dijkstra ② SPFA 加 SLF/LLL 优化 ③ 了解风险，灵活选择算法。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

int n, m, s;
vector<pair<int,int>> adj[10005];  // 邻接表：{终点, 权值}
int dist[10005];                    // 最短距离
bool in_queue[10005];               // 标记节点是否在队列中
int cnt[10005];                     // 入队次数（用于检测负环）

// ========== SPFA 核心 ==========
bool spfa() {
    // 初始化
    for (int i = 1; i <= n; i++) dist[i] = INF;
    dist[s] = 0;
    
    queue<int> q;
    q.push(s);           // 起点入队
    in_queue[s] = true;  // 标记在队列中
    cnt[s]++;             // 入队次数+1

    while (!q.empty()) {
        int u = q.front(); q.pop();
        in_queue[u] = false;  // 出队，取消标记

        // 松弛 u 的所有出边
        for (auto [v, w] : adj[u]) {
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;  // 松弛成功
                cnt[v]++;               // 入队次数+1
                if (cnt[v] >= n) return false;  // 负环检测！
                if (!in_queue[v]) {     // v不在队列中才入队
                    q.push(v);
                    in_queue[v] = true;
                }
            }
        }
    }
    return true;  // 无负环
}

// ========== 主函数 ==========
int main() {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        adj[u].push_back({v, w});  // 建有向边
    }
    if (spfa()) {
        for (int i = 1; i <= n; i++)
            printf("%d ", dist[i] == INF ? 2147483647 : dist[i]);
    } else {
        printf("存在负环！\n");
    }
}

🔑 负环检测原理

📐 为什么入队次数 ≥ n 就有负环？

在无负环的图中，任意节点的最短路最多经过 n-1 条边。
因此每个节点最多被松弛 n-1 次 → 最多入队 n-1 次。
如果某节点入队次数 ≥ n，说明它被松弛了超过 n-1 次 → 存在负环！
负环使路径可以无限缩短，节点会被反复松弛入队。

📊 四种最短路算法全景对比

算法	适用	复杂度	负权边	核心思想	优缺点
Dijkstra（堆优化）	单源	O((n+m)log n)	❌	贪心+优先队列	最快/不能负权
Bellman-Ford	单源	O(nm)	✅	松弛n-1轮	万能/太慢
SPFA	单源	平均O(m) 最坏O(nm)	✅	队列优化BF	快/可能被卡
Floyd	全源	O(n³)	✅	DP枚举中转点	代码短/n≤300

⚡ 选择策略：
• 边权非负 → Dijkstra（首选，稳定高效）
• 有负权边 + 需要判负环 → SPFA（注意被卡风险）
• 有负权边 + 需要严格复杂度 → Bellman-Ford（慢但安全）
• 全源最短路 + n≤300 → Floyd（3行代码搞定）

🎯 全源最短路问题（All-Pairs Shortest Path, APSP）
给定图 G=(V,E)，求每一对顶点 (i, j) 之间的最短距离。
对比单源：可以跑 n 次 Dijkstra，但 Floyd 用 DP 一步到位！代码只有 3 行核心。

💡 DP 思想 — 逐步枚举中转点

状态定义：设 dp[k][i][j] = 从 i 到 j，只允许经过节点 1,2,...,k 作为中转的最短距离。

状态转移方程（核心！）：

dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])

含义：从 i 到 j，要么不经过 k（保持 dp[k-1][i][j]），要么经过 k 中转（拆成 i→k 和 k→j 两段）

为什么枚举 k 是充分的？
任意一条最短路 i → ... → j，一定经过某些中间节点。当 k 枚举到路径上编号最大的中间节点时，这条路径就一定能被找到！

为什么 k 必须是最外层循环？
因为 dp[k] 依赖 dp[k-1]。必须先固定中转点 k，再遍历所有 (i,j) 对。若 k 在内层，则 dp[i][j] 被更新时用到的 dp[i][k] 可能已经是「经过更大编号中转」的值，破坏了 DP 的无后效性！

📦 滚动数组优化：三维 → 二维

观察：dp[k] 只依赖 dp[k-1]，所以可以就地更新（滚动数组）：

dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])

严格证明可以直接覆盖：
第 k 轮更新 dp[i][j] 时用到 dp[i][k] 和 dp[k][j]。
问：dp[i][k] 在本轮会被改变吗？答：dp[i][k] = min(dp[i][k], dp[i][k]+dp[k][k]) = min(dp[i][k], dp[i][k]+0) = dp[i][k]。
同理 dp[k][j] 也不会变。所以就地覆盖是安全的！

📈 Floyd 复杂度

时间复杂度推导：
三重循环：k 从 1 到 n，i 从 1 到 n，j 从 1 到 n
每层循环各执行 n 次，内层操作 O(1)

T(n) = n × n × n × O(1) = O(n³)

空间复杂度：dp 数组 n×n → O(n²)

适用条件：n ≤ 300（n³ = 2.7×10⁷，1秒内可完成）

🖼️ 示例图（4节点有向图）

边：1→2(3), 2→3(1), 3→4(2), 4→1(5), 1→3(8)
初始矩阵 dp[0]：
dp[i][j] = 边权（有边），∞（无边），0（i=j）

📊 四轮矩阵更新过程

⚠️ 矩阵更新易错点：
① k=1时，只有 dp[4][2] 和 dp[4][3] 被更新（因为只有节点4有边到节点1）。其他行 dp[i][1]=∞，无法通过1中转。
② k=2时，dp[1][3]=dp[1][2]+dp[2][3]=3+1=4（比原来的8更短！），dp[4][3]=dp[4][2]+dp[2][3]=8+1=9。
③ ∞+任何数=∞，不参与更新。实际代码中 INF 要注意加法不溢出。

#include <bits/stdc++.h>
using namespace std;

// ========== 常量 ==========
const int N = 205, INF = 0x3f3f3f3f;  // n≤200, INF≈10^9 防溢出
int n, m;
int dist[N][N];  // dist[i][j] = i到j的最短距离

// ========== Floyd 核心 ==========
void floyd() {
    for (int k = 1; k <= n; k++)          // 最外层：枚举中转点 k
        for (int i = 1; i <= n; i++)      // 中层：枚举起点 i
            for (int j = 1; j <= n; j++)  // 内层：枚举终点 j
                if (dist[i][j] > dist[i][k] + dist[k][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];  // 经k中转更短，更新
                }
}

// ========== 主函数 ==========
int main() {
    memset(dist, 0x3f, sizeof(dist));       // 初始化为无穷大
    for (int i = 1; i <= n; i++)
        dist[i][i] = 0;                      // 自身到自身距离为0
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        dist[u][v] = min(dist[u][v], w);     // 重边取最小权值
    }
    floyd();
    // 查询: dist[i][j] 就是 i 到 j 的最短距离
    // 若 dist[i][j] == INF，则 i 到 j 不可达
    return 0;
}

📊 Floyd vs n次Dijkstra 对比

对比项	Floyd	n次Dijkstra
时间复杂度	O(n³)	O(n(n+m)log n)
空间复杂度	O(n²)	O(n+m)
实现难度	⭐ 3行核心代码	⭐⭐⭐ 需邻接表+堆
支持负权边	✅ 可以（无负环时）	❌ 不可以
适用场景	n ≤ 300，稠密图	n,m 较大，稀疏图
代码量	极少	较多

⚠️ Floyd 易错点：
① 三重循环顺序：k 必须是最外层！先枚举中转点，再枚举起终点。顺序错了结果全错！
② 重边处理：建图时对同一条边取 min(dist[u][v], w)
③ dist[i][i] = 0 初始化不能忘
④ INF 用 0x3f3f3f3f 而不是 INT_MAX，避免 dist[i][k]+dist[k][j] 加法溢出

🎯 欧拉路径（Euler Path）：经过图中每条边恰好一次的路径。
🎯 欧拉回路（Euler Circuit）：经过图中每条边恰好一次且回到起点的闭合路径。
别名：一笔画问题 —— 能否一笔画完图形且不重复任何一条线？

📐 存在性条件的数学证明

无向图欧拉回路的充要条件：所有顶点度数为偶数，且图连通

必要性（→）：若存在欧拉回路，则每个顶点度数为偶数。
① 回路经过每条边恰好一次。
② 对于任意节点 v（非起点），回路每次「进入」v 消耗 1 度，「离开」v 消耗 1 度。
③ 进入和离开成对出现 → 每次经过 v 消耗 2 度。
④ 起点 = 终点（回路），先离开再最终回来，也消耗 2 度。
⑤ 因此每个节点的度数 = 2 × (经过次数) → 必为偶数。

充分性（←）：若所有顶点度数为偶数且图连通，则一定存在欧拉回路。
① 从任意点出发，沿未走过的边走。因为每个点度数为偶数，
每次进入一个点，都有一条未走边可离开。
② 唯一可能走不动的情况是回到了起点（用完了最后一条边）。
③ 若还有未走的边，从环上某个有未走边的节点出发，再走一个新环。
④ 将新环拼接进原环。重复此过程直到所有边被走完。
⑤ 这就是 Hierholzer 算法的正确性基础！

无向图判定规则：

欧拉回路 ⟺ 全偶数度 + 连通

欧拉路径 ⟺ 恰好 0 或 2 个奇度 + 连通

2个奇度时：路径必须从一个奇度点出发，到另一个奇度点结束。
0个奇度时：从任意点出发都是回路。

有向图判定规则：

欧拉回路 ⟺ 每点入度=出度 + 弱连通

欧拉路径 ⟺ 最多1点出-入=1（起点），最多1点入-出=1（终点），其余入=出

证明类似：每次经过消耗 1入度+1出度。
回路：每点进出相等。路径：起点多1次出发，终点多1次到达。

⚠️ 判定易错点：
① 连通性是前提！全偶度但不连通 → 没有欧拉回路。
② 奇度点数量只能是 0 或 2（无向图欧拉路径），不可能是其他值。
③ 有向图判定时，注意区分「弱连通」（忽略方向后连通）和「强连通」。欧拉路只需要弱连通。

🌍 欧拉路的实际应用

✏️ 一笔画问题：
判断图形能否一笔画出（不重复走任何边）。欧拉路径存在 ⟺ 可以一笔画！

📮 中国邮递员问题：
邮递员走遍所有街道至少一次后回到邮局，求最短路线。利用欧拉回路 + 最小权匹配。

🔌 电路布线：
PCB 板上测试所有连线，探针需走遍所有线路。建模为欧拉路径问题。

🧬 DNA 片段组装：
将短 DNA 片段拼接成完整序列。构建 de Bruijn 图 → 找欧拉路径！

📐 实例：一笔画问题

给定一个图形（如"日"字、"田"字），判断能否一笔画出。
解法：将交叉点视为节点，线段视为边，建图后检查度数条件。
• "日"字：2个奇度点（上下中点）→ 存在欧拉路径，可以一笔画！
• "田"字：4个奇度点（内部4个交叉点）→ 不存在欧拉路径，不能一笔画！

💡 度数计算验证（情况2）：
A: 连B、C → deg=2(偶) | B: 连A、C、D → deg=3(奇) | C: 连A、B → deg=2(偶) | D: 连B → deg=1(奇)
奇度点 = {B, D}，恰好2个 → 欧拉路径从B到D（或D到B）。
路径 B→A→C→B→D: 使用边 B-A✓, A-C✓, C-B✓, B-D✓，共4条边全部用完 ✅

💡 Hierholzer 算法步骤

⚡ 核心思想：从任意点出发，沿未走过的边走，直到走不动（回到起点形成环）。
然后检查环上是否还有未走边的节点，从它出发再走一个环，把新环拼接进去。
用栈实现拼接：遇到死胡同时把节点压入栈，回溯时拼接路径。

1

从起点沿未走边走

→

2

走不动→压栈

→

3

回溯检查

→

4

有未走边→继续

→

5

栈逆序=回路

🖼️ SVG图解：Hierholzer 逐步执行

💡 关键理解：Hierholzer 不是先找到完整回路，而是先走一个小环，再从环上找「分叉」走新环，逐步拼接。栈保证了拼接的正确顺序。时间复杂度 O(m)，每条边恰好访问一次。

📝 洛谷 P7771【模板】欧拉路径
给定有向图，求字典序最小的欧拉路径。若不存在输出 No。

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;

vector<int> adj[N];     // 有向图邻接表
int in_deg[N], out_deg[N]; // 入度、出度
int cur[N];                // 指针：记录每个点扫到哪了
vector<int> path;         // 欧拉路径（后序逆序输出）
int n, m;

// ========== Hierholzer 核心 ==========
void hierholzer(int u) {
    while (cur[u] < adj[u].size()) {
        int v = adj[u][cur[u]++];  // 按排序顺序取下一条边
        hierholzer(v);             // 递归走到下一个节点
    }
    path.push_back(u);  // 走不动了 → 后序入栈
}

// ========== 主函数 ==========
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        adj[u].push_back(v);   // 有向边 u → v
        out_deg[u]++; in_deg[v]++;
    }

    // ===== 第1步：排序邻接表（保证字典序最小）=====
    for (int i = 1; i <= n; i++)
        sort(adj[i].begin(), adj[i].end());

    // ===== 第2步：检查存在性（度数条件）=====
    int start = -1, end = -1, cnt = 0;
    for (int i = 1; i <= n; i++) {
        int d = out_deg[i] - in_deg[i];
        if (d == 1)      { cnt++; start = i; }  // 起点：出度比入度大1
        else if (d == -1) { cnt++; end = i; }    // 终点：入度比出度大1
        else if (d != 0)  { puts("No"); return 0; }
    }
    if (cnt != 0 && cnt != 2) { puts("No"); return 0; }

    // ===== 第3步：确定起点 =====
    if (start == -1)  // 所有点入度=出度 → 欧拉回路，从1开始
        start = 1;

    // ===== 第4步：跑 Hierholzer =====
    hierholzer(start);

    // ===== 第5步：检查连通性 =====
    if ((int)path.size() != m + 1) {
        puts("No"); return 0;  // 路径长度 ≠ m+1 → 图不连通
    }

    // ===== 第6步：逆序输出 =====
    reverse(path.begin(), path.end());
    for (int i = 0; i <= m; i++)
        printf("%d%c", path[i], i < m ? ' ' : '\n');
}

🔑 代码要点

1️⃣ cur[] 指针数组：
记录每个点当前扫到第几条边，避免重复扫描已走过的边，复杂度 O(n+m)。

2️⃣ 排序保证字典序：
建图后对每个点的邻接表 sort，每次按编号从小到大走边，保证路径字典序最小。

⚠️ 欧拉路易错点：
① 必须先检查度数条件再跑算法！不满足直接输出 No。
② 连通性检查：Hierholzer 结束后检查路径长度 = m+1 即可。
③ 起点选择：欧拉回路（cnt=0）从任意点出发；欧拉路径（cnt=2）必须从出度大的点出发。
④ 递归深度：m 条边最多递归 m 层，注意栈溢出风险，大数据可用显式栈。

编号	题目	知识点	难度
1	P4779 【模板】单源最短路径（标准版）	Dijkstra 堆优化模板	普及
2	P3371 【模板】单源最短路径（弱化版）	Dijkstra 朴素版也能过	普及
3	P1339 [USACO09OCT] Heat Wave G	单源最短路基础	普及+/提高−
4	P1629 邮递员送信	正反向图各跑 Dijkstra	普及+/提高−
5	P3385 【模板】负环	SPFA 判负环	普及+/提高−
6	P1938 [USACO09NOV] Job Hunt S	SPFA 负权边最短路	普及
7	P1119 灾后重建	Floyd 按时间逐步加入中转点	普及+/提高−
8	P1613 跑路	Floyd + 倍增预处理	普及+/提高−
9	P2966 [USACO09DEC] Cow Toll Paths G	Floyd 变形 + 点权	提高
10	P7771 【模板】欧拉路径	Hierholzer 模板	普及+/提高−
11	P1341 无序字母对	欧拉路径 + 字典序最小	普及+/提高−
12	UVA10129 Play on Words	单词首尾建图判欧拉路径	普及+/提高−

参考答案思路

1. P4779：Dijkstra 堆优化模板，直接套板子
2. P3371：弱化版，朴素 Dijkstra O(n²) 也能过
3. P1339：标准单源最短路，Dijkstra 直接上
4. P1629：建正反向图，分别从 1 跑 Dijkstra，答案 = Σ(go[i]+back[i])
5. P3385：SPFA 判负环模板，统计入队次数 ≥ n 即有负环
6. P1938：边权取负（利润变花费），SPFA 求最短路
7. P1119：Floyd 本质应用，按时间排序逐步加入中转点 k
8. P1613：倍增预处理"1秒可达"的点对，再 Floyd 求最少秒数
9. P2966：Floyd 变形，枚举中转点时同时考虑路径边权和 + 途经最大点权
10. P7771：Hierholzer 模板，注意字典序最小需对邻接表排序
11. P1341：字母建图求欧拉路径，Fleury/Hierholzer + 字典序最小
12. UVA10129：单词首尾字母建有向图，判连通 + 判欧拉路径存在性

💡 做题建议：先做模板题（1-2、5、10）掌握各算法基本用法，再做基础应用（3-4、6），最后挑战 Floyd 变形（7-9）和欧拉路综合题（11-12）。Dijkstra 和 SPFA 的模板务必熟练默写！

🗺️ 最短路算法全景对比

算法	适用	复杂度	负权边	核心思想
Dijkstra（堆优化）	单源	O((n+m)log n)	❌	贪心选最小+优先队列
Dijkstra（朴素）	单源	O(n²)	❌	贪心选最小+遍历
Bellman-Ford	单源	O(nm)	✅	松弛n-1轮
SPFA	单源	平均O(m) 最坏O(nm)	✅	队列优化Bellman-Ford
Floyd	全源	O(n³)	✅	DP枚举中转点
n×Dijkstra	全源	O(n(n+m)log n)	❌	跑n次Dijkstra

🎯 选择策略速查

📍 边权非负 + 单源 → Dijkstra（堆优化）
竞赛首选，几乎万能。

📍 有负权边 + 单源 → SPFA
能检测负环。注意卡 SPFA 的数据。

📍 全源 + n≤300 → Floyd
代码极简，3行核心。

📍 全源 + 大图 → n×Dijkstra
边权非负时效率更高。

📌 今日核心收获

🎯 Dijkstra：贪心 + 松弛 + 优先队列 → 单源最短路之王
Floyd：三重循环 DP → 全源最短路最简实现
Bellman-Ford：暴力松弛n-1轮 → 能处理负权边 + 检测负环
SPFA：队列优化Bellman-Ford → 快但可能被卡
欧拉路：度数判定 → Hierholzer 栈拼接 → 一笔画

⚠️ 全局易错点汇总

Dijkstra：① 不能处理负权边 ② 懒删除的旧副本要跳过 ③ pair第一维是距离
Floyd：① k必须最外层 ② dist[i][i]=0 ③ INF加法防溢出 ④ 重边取min
Bellman-Ford：① 复杂度O(nm)太高 ② 提前结束优化 ③ 负环检测
SPFA：① 可能被卡常 ② 入队次数≥n=负环 ③ in_queue标记防重复入队
欧拉路：① 先判存在性再跑算法 ② 检查连通性 ③ 路径起点必须从奇度点出发

🚀 Day 04 预告：线段树应用（懒标记、动态开点、扫描线）。数据结构进阶，敬请期待！

🏆

Day 03 完结

最短路与欧拉路 · Shortest Path & Euler Path

📋 今日知识点回顾

✅ Dijkstra 贪心 + 优先队列优化 → 单源最短路
✅ Floyd-Warshall 三重循环DP → 全源最短路
✅ Bellman-Ford → 暴力松弛n-1轮，支持负权边
✅ SPFA → 队列优化Bellman-Ford，负环检测
✅ 欧拉路/回路 → 度数条件 + Hierholzer算法
✅ 完整代码模板 + 洛谷例题 + 逐步模拟

Day 04 预告：线段树应用 🔥

✏️

🛤️ Dijkstra 算法 — 问题引入与贪心思想

🛤️ Dijkstra 算法 — 松弛操作详解

🛤️ Dijkstra 算法 — 优先队列优化与复杂度

🛤️ Dijkstra 算法 — 完整代码（逐行注释）

🛤️ Dijkstra 例题 — P4779 完整模拟

🔔 Bellman-Ford — 核心思想与原理

🔔 Bellman-Ford — 完整代码（逐行注释）

🔔 SPFA — 队列优化的 Bellman-Ford

🔔 SPFA — 完整代码 + 负环检测

🌐 Floyd-Warshall — 问题引入与DP思想

🌐 Floyd — 距离矩阵逐步更新（详解）

🌐 Floyd-Warshall — 完整代码（逐行注释）

🔄 欧拉路/回路 — 定义与存在性证明

🔄 欧拉路 — 判定图解（三种情况）

🔄 Hierholzer算法 — 欧拉回路构造

🔄 Hierholzer — 有向图模板（逐行注释）P7771

📚 Day 03 题单 — 最短路 + 欧拉路

📝 Day 03 知识总结 + 算法全景对比