图论

本系列此前多次把「图」当作工具使用：DFS 专篇用遍历求连通分量与拓扑序，BFS 专篇求无权最短路，并查集维护动态连通性。但这些只是图论版图的入口。一旦边带上权重、方向、容量，问题就升级为：加权最短路径怎么求？用什么边把所有点最便宜地连起来？任务间的依赖与冲突如何形式化？这些才是图论的主体。

图论的价值分两层。第一层是建模：把实际问题翻译成「点 + 边 + 边上属性」的语言–城市是点、道路是带权边、工序是点、先后依赖是有向边、管道网络是带容量的图。第二层才是算法：建模完成后，从一个规模不大的算法族里挑出对应工具。本文按「存储 → 拓扑排序 → 最短路 → 最小生成树 → 二分图 → 网络流 → 欧拉路径」的顺序，把这一族工具一次讲透。

图的基本概念与术语

先统一术语。图 $G = (V, E)$ 由顶点集 $V$ 与边集 $E$ 组成，$n = |V|$、$m = |E|$。按边是否有方向分为有向图与无向图（无向边等价于一对方向相反的有向边）；按边是否带权分为无权图与带权图，权重可以表示距离、费用、容量等任意可加量。

围绕顶点与边有一族基本概念：

• 度（degree）：与顶点相连的边数。有向图中分入度（指向它的边数）与出度（它指出的边数）。
• 路径与回路：路径是首尾相接的边序列；起点终点相同的路径称回路（环）。
• 连通性：无向图中任意两点间有路径即连通，极大连通子图称连通分量；有向图的对应概念是强连通分量（任意两点互相可达）。
• 生成树：连通图的极小连通子图，恰含 $n-1$ 条边；不唯一，各边权之和最小者称最小生成树。
• DAG：有向无环图，是依赖关系、决策过程的标准模型。

一个常用的事实：$n$ 个点的连通图至少 $n-1$ 条边；树（无环连通图）的判定三要素「连通、$n-1$ 条边、无环」知二推一。度数握手定理 $\sum_v \deg(v) = 2m$ 则是许多判定题的第一步–例如欧拉路径的存在性就看奇度点个数。

图的存储：三种结构

存储是所有图算法的地基，选错结构足以让 $O(V + E)$ 的算法退化成 $O(V^2)$。三种主流结构各有射程。

邻接矩阵

g[i][j] 存边 $(i,j)$ 的权值（无权图用 bool），无边用 INF 或 0 标记。查任意两点邻接关系 $O(1)$，但空间 $O(V^2)$，且遍历一个点的所有邻居必须扫完一整行–边的总数可能只有 $m$，扫描代价却是 $n$。只适合 $n \le 5000$ 的稠密图，或需要 $O(1)$ 查边、做矩阵运算（Floyd、传递闭包）的场景。

邻接表（vector 动态版）

每个点挂一个 vector，存其所有出边。空间 $O(V + E)$，遍历邻居总代价与边数成正比，是绝大多数场景的默认选择。

#include <vector>

// 邻接表: adj[u] 存 u 的所有出边 (终点, 权值)
// 点数 n, 边数 m
int n, m;
std::vector<std::vector<std::pair<int, long long>>> adj(n);

void addEdge(int u, int v, long long w) {
  adj[u].push_back({v, w});
  // 无向图再加一条:
  // adj[v].push_back({u, w});
}

// 遍历 u 的所有出边:
// for (auto [v, w] : adj[u]) { ... }

链式前向星（数组模拟链表）

竞赛中更常见的写法：用三个数组模拟链表，head[u] 记录 $u$ 的第一条出边编号，next[e] 记录同起点的下一条边。空间连续、无动态分配、常数小；无向图按「成对存储」技巧编号（第 $i$ 条与第 $i \oplus 1$ 条互为反向边），异或即取反边，网络流里频繁用到。

#include <cstring>

const int MAXN = 100005, MAXM = 200005;
int head[MAXN], nxt[MAXM], eto[MAXM];
long long ew[MAXM];
int cnt = 0;                     // 边从 0 开始成对编号

void initGraph(int n) {
  memset(head, -1, sizeof(int) * n);
  cnt = 0;
}

void addEdge(int u, int v, long long w) {
  eto[cnt] = v; ew[cnt] = w;
  nxt[cnt] = head[u];            // 头插法
  head[u] = cnt++;
}

// 遍历 u 的出边:
// for (int e = head[u]; e != -1; e = nxt[e])
//     // eto[e] 终点, ew[e] 权值

三种结构对比

结构	空间	查边	遍历邻居	适用场景
邻接矩阵	$O(V^2)$	$O(1)$	$O(V)$	稠密图、Floyd、$n \le 5000$
vector 邻接表	$O(V+E)$	$O(\deg)$	$O(\deg)$	通用默认、代码简洁
链式前向星	$O(V+E)$	$O(\deg)$	$O(\deg)$	竞赛、需反边/删边（网络流）

两条工程经验：一是边数组按 $2m$ 开–无向图每条边要存两次；二是网络流必须用前向星或带 rev 索引的邻接表，因为增广时要同步修改反向边容量。

拓扑排序：DAG 上的线性化

拓扑排序把 DAG 的顶点排成序列，使每条有向边 $(u,v)$ 中 $u$ 排在 $v$ 前。它是「依赖关系」的标准答案：编译顺序（文件依赖）、课程安排（先修课）、任务调度（流水线工序），本质都是求拓扑序。

Kahn 算法

反复摘除入度为 0 的点：入度为 0 意味着无前置依赖，可立即输出；输出后删除其所有出边，让后继的入度递减，产生新的可输出点。用队列维护，$O(V + E)$。

#include <vector>
#include <queue>

// Kahn 拓扑排序: 返回拓扑序, 有环则返回空
std::vector<int> topoSort(
    const std::vector<std::vector<int>>& adj) {
  int n = adj.size();
  std::vector<int> indeg(n, 0);
  for (int u = 0; u < n; ++u)
    for (int v : adj[u]) ++indeg[v];   // 统计入度
  std::queue<int> q;
  for (int u = 0; u < n; ++u)
    if (indeg[u] == 0) q.push(u);
  std::vector<int> order;
  while (!q.empty()) {
    int u = q.front(); q.pop();
    order.push_back(u);
    for (int v : adj[u])
      if (--indeg[v] == 0) q.push(v);
  }
  return (int)order.size() == n
      ? order : std::vector<int>{};
}

输出点数不足 $n$，说明剩下的点都在环里–Kahn 顺带完成了有向图环检测。这与 DFS 三色标记法（DFS 专篇的环检测节）、并查集判无向环构成三种互补方案：Kahn 能同时给出拓扑序，DFS 能定位环的具体路径，并查集只适合无向图。

拓扑序不唯一（入度 0 的点可任选），需要字典序最小时把队列换成小根堆。另一个高价值应用是 DAG 上的 DP：按拓扑序递推，每条边恰好松弛一次，「最长路 / 传递闭包 / 概率累计」都能线性完成–这是很多「有依赖的最值问题」的正解，思路同 动态规划 的拓扑序递推。

最短路 I：Dijkstra

从本节起进入图论最庞大的家族：最短路。问题设定：给定起点 $s$，求 $s$ 到所有点的最短距离 $\text{dist}[\cdot]$。无权图已由 BFS 解决（$O(V+E)$，见 BFS 专篇）；边权任意时，BFS 的「先发现即最短」失效–边少但权大的路径可能输给边多但权小的路径，必须按距离而非层数组织扩展顺序。

贪心思想与正确性

Dijkstra 维护两个集合：已确定最短距离的点集 $S$ 与未确定的点集 $T$。每轮从 $T$ 中取 $\text{dist}$ 最小的点 $u$ 加入 $S$，并用 $u$ 的出边松弛邻居：$\text{dist}[v] \gets \min(\text{dist}[v], \text{dist}[u] + w(u,v))$。

正确性依赖边权非负。证明：取 $u$ 是 $T$ 中 $\text{dist}$ 最小的点，反设存在更短路径 $P: s \rightsquigarrow v \rightsquigarrow u$（$v$ 是路径上第一个还在 $T$ 中的点）。由于权非负，$P$ 上 $s$ 到 $v$ 的前缀不超过全长，即 $\text{dist}[v] \le \text{dist}'(u) < \text{dist}[u]$，与 $u$ 是 $T$ 中最小矛盾。若存在负权边，$\text{dist}[v] \le \text{dist}'(u)$ 这一步不成立，贪心崩溃–此时须换 Bellman-Ford。

堆优化实现

朴素实现每轮线性扫 $T$ 找最小，$O(V^2)$，稠密图（$m \approx n^2$）下反而最优。稀疏图用小根堆，$O(E \log E)$：

#include <vector>
#include <queue>

using pll = std::pair<long long, long long>;
const long long INF = 1e18;

// 堆优化 Dijkstra: adj[u] 存 (终点, 权值)
// 时间 O(E log E), 要求边权非负
std::vector<long long> dijkstra(
    const std::vector<std::vector<pll>>& adj,
    int s) {
  int n = adj.size();
  std::vector<long long> dist(n, INF);
  std::priority_queue<pll, std::vector<pll>,
                      std::greater<pll>> pq;
  dist[s] = 0;
  pq.push({0, s});                // (距离, 节点)
  while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;    // 陈旧条目, 跳过
    for (auto [v, w] : adj[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;    // 松弛成功
        pq.push({dist[v], v});
      }
    }
  }
  return dist;                    // INF 即不可达
}

两个关键细节：

• 惰性删除。松弛成功就入堆，旧条目不删除；弹出时若 d > dist[u] 说明 $u$ 已被更优条目处理过，跳过。堆大小 $O(E)$，每个点可能被松弛多次。
• 弹出即定局。配合非负权，每个点第一次以最终距离弹出。若只需到终点 $t$ 的距离，弹出 $t$ 时即可返回。

LeetCode 743「网络延迟时间」是标准套用：信号从节点 $k$ 发出，求最晚收到信号的节点的时间，即 $\max_{i} \text{dist}[i]$（不可达返回 $-1$）。

与 BFS 家族的衔接

把 BFS 的队列逐步升级：普通队列（边权全 1）→ 双端队列（边权 0/1，0-1 BFS）→ 优先队列（边权非负，Dijkstra）。这条「容器随权值复杂度递增」的演化线在 BFS 专篇 已有铺垫，Dijkstra 正是它的终点。进一步给堆的排序键加上启发式估计（到终点的估计距离），就得到 A*。

最短路 II：Bellman-Ford 与 SPFA

Bellman-Ford：暴力松弛的稳健

绕开贪心，改用全局松弛：对所有边执行 $\text{dist}[v] \gets \min(\text{dist}[v], \text{dist}[u] + w)$，重复 $n-1$ 轮。正确性基于最短路至多 $n-1$ 条边：第 $k$ 轮结束后，所有边数 $\le k$ 的最短路均已确定，$n-1$ 轮后覆盖全部。复杂度 $O(VE)$，慢但容忍负权边。

负环判定免费赠送：第 $n$ 轮仍有边可松弛，说明存在经过负环（可无限绕圈减距离）的最短路，此时「最短路」不存在。

SPFA：队列优化

Bellman-Ford 的浪费在于每轮松弛所有边，而只有上一轮被更新的点才可能引发新松弛。SPFA（Shortest Path Faster Algorithm）把被更新的点入队，只松弛队首点的出边：

#include <vector>
#include <queue>

using pll = std::pair<long long, long long>;
const long long INF = 1e18;

// SPFA: adj[u] 存 (终点, 权值), 允许负权边
// 返回 true 表示存在从 s 可达的负环
bool spfa(const std::vector<std::vector<pll>>& adj,
          int s, std::vector<long long>& dist) {
  int n = adj.size();
  dist.assign(n, INF);
  std::vector<bool> inq(n, false);
  std::vector<int> relaxCnt(n, 0);  // 松弛次数
  std::queue<int> q;
  dist[s] = 0; inq[s] = true; q.push(s);
  while (!q.empty()) {
    int u = q.front(); q.pop(); inq[u] = false;
    for (auto [v, w] : adj[u]) {
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        if (!inq[v]) {
          if (++relaxCnt[v] >= n) return true;
          q.push(v); inq[v] = true;
        }
      }
    }
  }
  return false;
}

判负环的依据：无负环时每点至多被松弛 $n - 1$ 次；某点松弛次数达 $n$，即有负环。SPFA 平均表现好（随机数据接近 $O(kE)$，$k$ 为小常数），但最坏 $O(VE)$ 且极易被构造数据卡掉。竞赛惯例：非负权必用 Dijkstra；含负权才考虑 SPFA，且默认出题人可能卡它，备 Bellman-Ford 或队列优化变体。

差分约束：负权最短路的建模典范

差分约束系统求变量 $x_i$ 满足一组形如 $x_v - x_u \le c$ 的不等式。注意到松弛不等式 $\text{dist}[v] \le \text{dist}[u] + w$ 与它同构：每条约束建边 $u \to v$ 权 $c$，加超级源点 $s$ 向所有点连 0 权边，跑一遍最短路，$\text{dist}[i]$ 即一组可行解；出现负环则系统无解。这是「图论建模力」的典型样本–不等式组、区间约束、进度安排问题都能这样翻译。

最短路 III：Floyd 与全源最短路

前面两个算法都是单源（一个起点）。若要所有点对的最短距离，对每个点跑一次 Dijkstra 得 $O(VE \log E)$；点数少（$n \le 500$）时，Floyd 的三重循环反而更简单直接：

#include <vector>

const long long INF = 1e18;

// Floyd: d 为 n×n 邻接矩阵, 原地更新
// d[i][i]=0, 无边为 INF
void floyd(std::vector<std::vector<long long>>& d) {
  int n = d.size();
  for (int k = 0; k < n; ++k)     // 中转点在最外层
    for (int i = 0; i < n; ++i) {
      if (d[i][k] == INF) continue;  // 剪枝兼防溢出
      for (int j = 0; j < n; ++j)
        if (d[i][k] + d[k][j] < d[i][j])
          d[i][j] = d[i][k] + d[k][j];
    }
}

DP 视角

Floyd 是动态规划：定义 $d^{(k)}[i][j]$ 为「只允许前 $k$ 个点作中转」时 $i$ 到 $j$ 的最短距离，则

$$d^{(k)}[i][j] = \min\left(d^{(k-1)}[i][j],\; d^{(k-1)}[i][k] + d^{(k-1)}[k][j]\right)$$

初值 $d^{(0)}$ 即邻接矩阵。第一维可滚动省略，但中转点 $k$ 必须在最外层循环–内层的 $d[i][j]$ 才能安全地混用新旧两层数据。把 $k$ 放最内层是新手最高频的写法错误，结果看似接近正确，实则漏解。

Floyd 允许负权边（不允许负环），复杂度 $O(n^3)$、代码五行，$n \le 500$ 时无脑可用。把 min/+ 换成 and/or 即得传递闭包（判任意两点连通/可达），是 Floyd 思想的直接迁移。

最短路算法选型表

算法	复杂度	负权边	负环检测	适用
BFS	$O(V+E)$	不允许	不能	无权图单源
Dijkstra（堆）	$O(E \log E)$	不允许	不能	非负权单源，默认首选
Bellman-Ford	$O(VE)$	允许	能	小规模 / 需稳健
SPFA	平均 $O(kE)$，最坏 $O(VE)$	允许	能	负权图，防卡慎用
Floyd	$O(n^3)$	允许（无负环）	能（对角线变负）	全源、$n \le 500$

最小生成树：Kruskal 与 Prim

换一个问题：给定无向连通带权图，选 $n-1$ 条边把所有点连通且总权值最小。这是网络布线的数学原型–电网、光纤、道路网的最低成本连通方案。与最短路的区别一目了然：最短路优化单点视角的路径，MST 优化全局的边集。

切割性质：两家算法共同的根

切割性质（cut property）：把点集划分为 $S$ 与 $V \setminus S$，跨越两边的边中权值最小的那条必在某个 MST 中。证明用交换论证：设最小横跨边 $e$ 不在 MST $T$ 中，加入 $e$ 必形成环，环上必有另一条横跨边 $e'$，且 $w(e') \ge w(e)$，用 $e$ 换掉 $e'$ 不增总权。两个经典算法都是切割性质的不同执行策略。

Kruskal：排序 + 并查集

把所有边升序排序，依次尝试加入；用并查集判断加入后是否成环（两端点已连通则弃），连通块合并 $n-1$ 次即停。

#include <vector>
#include <algorithm>
#include <functional>

struct Edge {
  int u, v; long long w;
};

// Kruskal: 返回 MST 总权值, 图不连通返回 -1
// 时间 O(E log E)
long long kruskal(std::vector<Edge>& es, int n) {
  auto byW = [](const Edge& a, const Edge& b) {
    return a.w < b.w;
  };
  std::sort(es.begin(), es.end(), byW);
  std::vector<int> parent(n);
  std::function<int(int)> find = [&](int x) {
    return parent[x] == x ? x
        : parent[x] = find(parent[x]);
  };
  for (int i = 0; i < n; ++i) parent[i] = i;
  long long total = 0;
  int taken = 0;
  for (const Edge& e : es) {
    int ru = find(e.u), rv = find(e.v);
    if (ru == rv) continue;       // 会成环, 弃
    parent[ru] = rv;              // 合并两连通块
    total += e.w;
    if (++taken == n - 1) break;
  }
  return taken == n - 1 ? total : -1;
}

Kruskal 的正确性可以看作贪心的切割性质证明样板：每一步选当前最小横跨边（各连通块之间的边界即切割），交换论证保证不劣。它与 Prim 有个精妙的不对称：Kruskal 全局排序边、逐步合并森林；Prim 从单点出发、逐步扩张一棵树。

Prim：从一点长出一棵树

维护已在树中的点集，每轮用堆取出「连接树内外的最小边」，把树外的端点吸收进来。与 Dijkstra 形神俱似–堆里存的都是「到已确定集合的最小距离」，区别只在 Dijkstra 累加路径长（$\text{dist}[u] + w$），Prim 只看边权本身（$w$）：

#include <vector>
#include <queue>

using pll = std::pair<long long, long long>;

// 堆优化 Prim: adj[u] 存 (终点, 权值)
// 稀疏图 O(E log V); 稠密图用朴素 O(V^2) 版
long long prim(
    const std::vector<std::vector<pll>>& adj) {
  int n = adj.size();
  std::vector<bool> inTree(n, false);
  std::priority_queue<pll, std::vector<pll>,
                      std::greater<pll>> pq;
  pq.push({0, 0});                // (边权, 树外点)
  long long total = 0;
  int taken = 0;
  while (!pq.empty() && taken < n) {
    auto [w, u] = pq.top(); pq.pop();
    if (inTree[u]) continue;      // 陈旧条目
    inTree[u] = true;
    total += w; ++taken;
    for (auto [v, wt] : adj[u])
      if (!inTree[v]) pq.push({wt, v});
  }
  return taken == n ? total : -1; // -1 不连通
}

选型口诀：稀疏图 Kruskal，稠密图朴素 Prim。Kruskal 只关心边集甚至不需要建邻接表（LeetCode 1584「连接所有点的最小费用」中边可按需生成）；Prim 适合已按邻接表存储、或点少边多的场景。另一个常考结论：若每条边权互不相同，MST 唯一；次小生成树 = 在 MST 上做「换一条边」的最小调整。

二分图：染色与匹配

判定：无奇环 ⇔ 二分图

若能把点集分成两半，使每条边都横跨两半，图为二分图。充要判定：不含奇数长度的环。沿环交替染色，偶环首尾相容、奇环首尾冲突。DFS 染色一遍即可，$O(V+E)$：

#include <vector>

// DFS 染色: color 全 -1 起步, c 取 0/1
bool colorize(int u, int c,
    const std::vector<std::vector<int>>& adj,
    std::vector<int>& color) {
  color[u] = c;
  for (int v : adj[u]) {
    if (color[v] == -1) {
      if (!colorize(v, c ^ 1, adj, color))
        return false;
    } else if (color[v] == c) {
      return false;               // 相邻同色: 奇环
    }
  }
  return true;
}

// 主函数: 对每个连通块从任意点染 0
// 全部成功 ⇔ 二分图 (LeetCode 785)

LeetCode 785「判断二分图」是裸判定；「可能的二分法」把「讨厌关系」建为边后同构。BFS 层序染色同样可行，且无爆栈之忧（DFS 专篇的迭代版讨论）。

匈牙利算法：最大匹配

匹配是边集两两不共端点；最大匹配求基数最大。经典场景：$n$ 个任务、$m$ 个工人，每人能做若干任务，最多同时安排多少对–任务与工人各成一侧、可行关系为边。

匈牙利算法的核心是增广路：一条从未匹配点出发、交替经过「非匹配边 / 匹配边」、终于另一侧未匹配点的路径。把增广路上的边取反（非匹配变匹配），匹配数恰加一。算法对每个左部点 DFS 找增广路，找不到即该点无望：

#include <vector>

// 匈牙利算法: O(V·E)
// adj[u]: 左部点 u 可连的右部点列表
bool tryAssign(int u,
    const std::vector<std::vector<int>>& adj,
    std::vector<bool>& vis,
    std::vector<int>& match) {
  for (int v : adj[u]) {
    if (vis[v]) continue;
    vis[v] = true;
    // v 空闲, 或其原配能让位
    if (match[v] == -1 ||
        tryAssign(match[v], adj, vis, match)) {
      match[v] = u;               // 占住 v
      return true;
    }
  }
  return false;
}

int hungarian(
    const std::vector<std::vector<int>>& adj,
    int rightSize) {
  std::vector<int> match(rightSize, -1);
  int ans = 0;
  for (int u = 0; u < (int)adj.size(); ++u) {
    std::vector<bool> vis(rightSize, false);
    if (tryAssign(u, adj, vis, match)) ++ans;
  }
  return ans;
}

vis 必须每个左部点重置–它在单次增广里防止两个任务争抢同一个右部点。二分图存在完美匹配的充要条件（Hall 定理）与「最大匹配 = 最小点覆盖」（König 定理）是这一分支的两块理论基石，后者把「匹配」与「覆盖」两个看似无关的问题划上等号。需要边带权的最大匹配时升级为 KM 算法或最小费用最大流。

网络流：最大流与最小割

网络是带源点 $s$、汇点 $t$ 的有向图，每条边有容量上限。最大流问：$s$ 到 $t$ 最多能输送多少流量？这是物流、通信、调度问题的公共骨架。

残量网络与增广路

任何最大流算法共享同一框架–Ford-Fulkerson 方法：维护残量网络（每条边剩余可流量），只要存在 $s \to t$ 的正容量路径（增广路），就沿它推送流量并更新残量，直至无路可走。关键设计是反向边：为每条容量边预留一条初始为 0 的反向边，增广时同步「正减反加」。反向边是反悔机制–它允许后续流量撤销之前的错误分配，改走更优路线。没有它，算法会因贪心路径选错而得出次优答案。

BFS 找增广路（Edmonds-Karp，$O(VE^2)$）保证每次增广最短，避免 Ford-Fulkerson 在容量大时绕圈。竞赛主流是 Dinic：BFS 建分层图 + DFS 多路增广 + 当前弧优化，$O(V^2 E)$，实际常数极小：

#include <vector>
#include <queue>
#include <climits>

struct Dinic {                     // O(V^2 E)
  struct E { int to; long long cap;
             int rev; };           // rev: 反边下标
  std::vector<std::vector<E>> g;
  std::vector<int> level, cur;
  explicit Dinic(int n)
      : g(n), level(n), cur(n) {}

  void addEdge(int u, int v, long long c) {
    g[u].push_back({v, c, (int)g[v].size()});
    g[v].push_back({u, 0,          // 反边初始 0
                    (int)g[u].size() - 1});
  }

  bool bfs(int s, int t) {         // 建分层图
    std::fill(level.begin(), level.end(), -1);
    std::queue<int> q;
    level[s] = 0; q.push(s);
    while (!q.empty()) {
      int u = q.front(); q.pop();
      for (const E& e : g[u])
        if (e.cap > 0 && level[e.to] < 0) {
          level[e.to] = level[u] + 1;
          q.push(e.to);
        }
    }
    return level[t] >= 0;
  }

  long long dfs(int u, int t, long long f) {
    if (u == t) return f;
    for (int& i = cur[u];          // 当前弧: 不回头
         i < (int)g[u].size(); ++i) {
      E& e = g[u][i];
      if (e.cap > 0 &&
          level[e.to] == level[u] + 1) {
        long long d =
            dfs(e.to, t, std::min(f, e.cap));
        if (d > 0) {
          e.cap -= d;              // 正向减容
          g[e.to][e.rev].cap += d; // 反向增容
          return d;
        }
      }
    }
    return 0;
  }

  long long maxflow(int s, int t) {
    long long flow = 0;
    while (bfs(s, t)) {
      std::fill(cur.begin(), cur.end(), 0);
      while (long long f =
                 dfs(s, t, LLONG_MAX))
        flow += f;
    }
    return flow;
  }
};

当前弧优化（cur）的含义：一次分层内，某条边已流尽后不再重扫，DFS 的总代价被摊还到 $O(VE)$。

最小割定理

最大流 = 最小割：$s$ 到 $t$ 的最大流量，等于割断 $s,t$ 所需的最小边容量和。这一定理（Ford-Fulkerson 定理）让「最多输送多少」与「最少删哪些边能阻断」两个对偶问题同解，正确性由残量网络无增广路时的割构造直接给出。建模威力巨大：项目选取（收益冲突）、棋盘放棋、逃生路径均能翻译成最小割。「文理分科、二选一冲突」类问题的标准套路是：$s$ 连收益、$t$ 连代价、冲突边连 $+\infty$，总收益 = 收益和 - 最小割。

欧拉路径：一笔画问题

七桥问题的后代：经过每条边恰好一次的路径叫欧拉路径，回到起点的叫欧拉回路。它与哈密顿路径（经过每个点一次）形似神异–欧拉看边，存在性有线性判据；哈密顿看点，判定是 NP 完全问题。

存在性判定

度数直接给出答案（连通前提下）：

• 无向图：奇度点个数为 0 → 存在欧拉回路；恰为 2 → 存在欧拉路径（两奇点为端点）；否则不存在。
• 有向图：所有点入度 = 出度 → 欧拉回路；恰有一点出度 = 入度 + 1（起点）、一点入度 = 出度 + 1（终点）、其余平衡 → 欧拉路径。

直觉：每次进入一个中间点必须再离开，边不重不漏意味着进出配对，度数必须成对（有向则出入平衡）；只有路径端点允许单数。

Hierholzer 算法

判定通过后，线性构造路径。核心观察：从某个点走到无路可走时，它必然是路径端点；把走过的边删除后，图仍平衡，剩余部分可逐步「补洞」。实现上等价于一棵「删边版 DFS」：每条边访问即删（防重走），点在后序（无路可走时）入栈，最终栈从底到顶即欧拉路径（逆序输出）：

#include <vector>

// Hierholzer(有向图): it 为各点当前弧
// circuit 逆序即欧拉路径
void hierholzer(int u,
    const std::vector<std::vector<int>>& adj,
    std::vector<int>& it,
    std::vector<int>& circuit) {
  while (it[u] < (int)adj[u].size()) {
    int v = adj[u][it[u]++];      // 访问即删边
    hierholzer(v, adj, it, circuit);
  }
  circuit.push_back(u);           // 无路可走才入栈
}

无向图版本须把边成对编号（链式前向星天然支持），访问第 $e$ 条边时同时标记 $e$ 与 $e \oplus 1$ 为已用。「骑马修栅栏」（洛谷 P2731）是标准练习：求字典序最小的欧拉路径，先按终点排序邻接表再跑 Hierholzer 即可。

横向对比：图论算法速查表

问题	首选算法	复杂度	前置条件
连通分量	DFS/BFS	$O(V+E)$	—
动态连通	并查集	均摊 $O(\alpha)$	离线或增量
依赖排序 / DAG 判环	Kahn	$O(V+E)$	有向图
无权单源最短路	BFS	$O(V+E)$	边权全 1
非负权单源最短路	Dijkstra（堆）	$O(E \log E)$	无负权
负权单源 / 负环检测	SPFA / Bellman-Ford	最坏 $O(VE)$	无负环可解
全源最短路	Floyd	$O(n^3)$	$n \le 500$，无负环
最小生成树	Kruskal / Prim	$O(E \log E)$ / $O(V^2)$	无向连通
二分图判定	染色	$O(V+E)$	—
二分图最大匹配	匈牙利	$O(VE)$	二分图
最大流 / 最小割	Dinic	$O(V^2 E)$	容量非负
欧拉路径	Hierholzer	$O(V+E)$	度数平衡

记忆主线只有一条：先识别问题原型（连通 / 可达 / 最短 / 最小连接 / 匹配 / 流通 / 一笔画），再套对算法。识别的关键在建模阶段就把「点是什么、边是什么、边权 / 容量是什么」写清楚。

实战场景：竞赛与工程

竞赛

• 建图是第一道坎。差分约束（不等式 → 负权边）、缩点（SCC 当超级点，见 DFS 专篇 Tarjan 节）、分层图（状态拆点：$u$ 复制 $k$ 层表示剩余油量 / 免费次数）是三大高频套路。图论题一半难度在建模，一半在模板。
• 最短路家族的分寸感：非负权堆 Dijkstra 一把梭；负权 SPFA 慎入（可能被卡，出题人常用网格菊花图 hack）；全源小图 Floyd 五行保平安。
• 网络流是「难题收容所」：二元决策、割的语义、路径不相交、棋盘放置都能翻译。模板（Dinic + 费用流）须滚瓜烂熟，赛场只剩建图。
• 精度与范围：距离和可达 $10^{18}$ 量级，int 必炸；树上的边权路径统计要换 long long。

工程

• 路由协议：OSPF 每个路由器以自己为源跑 Dijkstra 得最短路径树，是「分布式 Dijkstra」的教科书案例；BGP 的策略选路则是带约束的最短路变体。
• 地图导航：边权 = 实时路况的动态加权图，量产方案是分层图 + A*（收缩层级把远距离查询压到毫秒级，见 BFS 专篇 的 A* 节）。
• 任务编排：CI/CD 流水线、编译器依赖分析、大数据调度（Airflow 类系统）都以 DAG 建模，拓扑序决定执行顺序，关键路径（DAG 最长路）决定总工期。
• 推荐与匹配：二分图匹配出现在打车派单、广告分配、课程排课；成本敏感场景升级为最小费用最大流。

常见陷阱与边界条件

1. 无向边忘记加两次：邻接表 / 前向星都要 $u \to v$、$v \to u$ 各一条，忘加则图「变单向」，连通性 / 最短路全错。
2. INF 溢出：INF 取 0x7fffffff 时 dist[u] + w 直接溢出为负；用 1e18 并在松弛前判断可达性，Floyd 尤其要防 INF + INF。
3. Dijkstra 遇负权：贪心的「弹出即定局」失效，答案错且无报错。数据有负权必换 SPFA / Bellman-Ford。
4. Floyd 循环层次写反：$k$ 必须在最外层；写在内层结果似是而非，随机数据都测不出。
5. SPFA 裸奔：竞赛中未加优化的 SPFA 是出题人的首选攻击目标，谨慎使用或备 Bellman-Ford 兜底。
6. 链式前向星初始化：head 忘记置 -1、cnt 未清零，遍历直接越界；memset(head, -1, sizeof(int) * n) 而非整个数组可省时间。
7. 拓扑排序自环：自环使点入度含自身，Kahn 输出不足 $n$ 判环即可捕获，但若题面允许自环需单独过滤。
8. 匈牙利 vis 未按轮重置：vis 是「本轮增广」的临时标记，跨轮残留会把可行增广路堵死。
9. Dinic 漏反边 / 漏当前弧：反边容量不加，反悔机制失效；cur 不重置或不推进，同一轮反复扫废边，TLE。
10. 欧拉判定漏连通性：度数平衡但图不连通（非端点所在分量），不存在欧拉路径；先判连通再数度。
11. MST 的存在性：图不连通时没有生成树，Kruskal 收不满 $n-1$ 条边应返回失败而非部分和。
12. 重边处理：Dijkstra / MST / 匈牙利天然兼容重边；但「删一条边判桥」类问题重边是两条独立边，不能用「v == parent」跳过。

小结

图论的三句话本质：

1. 建模先行：一切图算法的输入是「点 + 边 + 属性」的抽象，把实体翻译成图，问题就解决了一半。
2. 松弛与贪心贯穿最短路：Dijkstra 是非负权下的贪心松弛，Bellman-Ford 是无条件暴力松弛，Floyd 是中转点递推的 DP 松弛–家族内部一脉相承。
3. 交换论证与反悔机制是结构性最优的钥匙：MST 靠切割性质换边，网络流靠反向边反悔，匈牙利靠增广路腾位。

与系列其他篇目的关系：遍历与连通性见 DFS 专篇 与 BFS 专篇，动态连通见 并查集，Kruskal 的排序贪心见 贪心，Floyd / DAG 递推的 DP 视角见 动态规划。图论不是孤立专题，而是把这些零件装配成整机的地方–掌握本文的选型表与各模板，面对陌生问题时先问「点是什么、边是什么」，算法往往已经写完了一半。