图算法的重点是建模

很多图算法题表面上不说图。

它可能说的是：

  • 使用一次折扣券，找最便宜路线
  • 选择一组课程，使先修关系满足
  • 给学生分配项目
  • 判断城市之间是否能互相到达
  • 从起点到终点，路径边数必须是 3 的倍数
  • 搬运供需，最小化运输成本

这些题的核心都不是“写 BFS”或“写 Dijkstra”。

核心是把原问题里的对象、状态、约束、目标，编码成图。

最重要的一句话：

节点 = 状态，边 = 状态转移，权重 = 代价。

建图五问

不管什么题，先问这五个问题：

1. 我最终需要知道什么？
        ↓
2. 这个“什么”依赖哪些中间状态？
        ↓
3. 每个状态如何从已知量转移过来？
        ↓
4. 图的节点/边应该编码什么信息？
        ↓
5. 起点终点是什么？跑什么算法？

如果题目只是标准最短路，节点就是原图节点，边就是道路，权重就是距离。

如果题目多了限制，节点通常就不能只表示位置。它还要表示“当前已经用了几次操作”“上一条边是什么颜色”“当前步数 mod k 是多少”。

这就是状态扩张。

先看图的基本结构

建模后，先按结构选算法：

图结构 / 权重条件先想到
无权图BFS
非负边权Dijkstra
有负边权，无负环Bellman-Ford
DAGTopological order + DP
所有点对最短路Floyd-Warshall / Johnson
无向图连通性DFS / BFS
有向图互相可达SCC

这里的判断来自算法前提。

Dijkstra 需要非负边权。Bellman-Ford 可以处理负边，但成本更高。DAG 上即使有负边，也可以按拓扑序做 DP，因为没有环。

算法不是按喜好选的，是按图结构和约束选的。

Layered Graph：给路径加状态

Layered graph 适合所有“路径 + 有限状态”的问题。

典型信号：

  • 有一张 coupon
  • 可以对最多两条边减半
  • 边数必须满足 mod k
  • 路径必须使用某几类颜色
  • 某个特殊操作最多用几次

原图节点是 $v$，扩展后节点变成：

$$ (v, state) $$

state 记录当前已经发生了什么。

一次折扣

题目：从 $s$ 到 $t$，可以让一条边半价，求最短路。

构造：

  • $V' = V \times \{0,1\}$
  • $(v,0)$ 表示到达 $v$ 且还没用折扣
  • $(v,1)$ 表示到达 $v$ 且已经用过折扣

对每条原边 $(u,v)$，权重为 $w(u,v)$：

  • $(u,0) \to (v,0)$，权重 $w(u,v)$
  • $(u,1) \to (v,1)$，权重 $w(u,v)$
  • $(u,0) \to (v,1)$，权重 $w(u,v)/2$

然后求：

$$ (s,0) \to (t,1) $$

或者如果允许不用折扣，也可以取 $(t,0)$ 和 $(t,1)$ 的 min。

这里的关键在于状态必须记录折扣是否已经使用，“复制两层图”只是实现这个状态记录的方式。

边数 mod k

题目：从 $s$ 到 $t$，路径边数必须能被 $k$ 整除。

状态记录当前走了多少条边 mod $k$。

构造：

  • $V' = V \times \{0,1,\ldots,k-1\}$
  • 若原图有边 $(u,v)$，则新图中有：
$$ (u,i) \to (v,(i+1)\bmod k) $$

权重保持不变。

目标：

$$ (s,0) \to (t,0) $$

这个建模非常通用。凡是路径上有一个有限状态机一样的限制，都可以把 finite state 乘到节点上。

颜色约束

如果限制是“相邻边颜色不能相同”，状态可以记录上一条边颜色。

节点从 $v$ 变成：

$$ (v, lastColor) $$

如果限制是“必须至少用过红边和蓝边”，状态可以记录已经用过的颜色集合：

$$ state \in \{0, R, B, RB\} $$

红边负责把：

  • $0 \to R$
  • $B \to RB$

蓝边负责把：

  • $0 \to B$
  • $R \to RB$

普通边留在同一层。

这类题不要把颜色当成边的附属信息看完就算了。颜色会影响未来能怎么走，所以它必须进入状态。

反向图 + 两次最短路

题目：求从 $s$ 到 $t$ 的最短路径，但路径必须经过集合 $A$ 中某个点。

直接枚举每个 $a \in A$，求：

$$ dist(s,a) + dist(a,t) $$

第一项可以从 $s$ 在原图跑一次最短路得到。

第二项如果对每个 $a$ 都跑一次，就太慢。

技巧是建反向图，从 $t$ 跑一次最短路。反向图上从 $t$ 到 $a$ 的距离，等于原图上从 $a$ 到 $t$ 的距离。

所以答案是：

$$ \min_{a \in A} dist_s[a] + dist_t^{rev}[a] $$

这类技巧的核心是：很多“到终点的距离”可以通过反向图一次性预处理。

SCC 缩点

有向图里的 strongly connected component（SCC）是互相可达的一组点。

把每个 SCC 缩成一个点，得到的图一定是 DAG。

流程：

第1步：求 SCC
第2步：缩点得到 DAG H
第3步：在 DAG H 上做 DP / DFS / 拓扑排序

这个套路适合：

  • 找所有在环上的点/边
  • 缩点后做可达性
  • 缩点后做最大收益
  • 判断图结构性质
  • 在 SCC 之间做路径统计

为什么缩点后是 DAG？

如果缩点图里还有一个有向环，那么这些 SCC 之间其实互相可达，应该属于同一个 SCC，矛盾。

SCC 的建模意义

SCC 缩点的价值是把“内部随便走”的复杂结构压成一个节点。

在一个 SCC 内部，任意两个点互相可达，所以对外部决策来说，它们常常可以看成一个整体。

比如想找最少选几个起点，使得所有点都可达。

缩点成 DAG 后，只需要在每个入度为 0 的 source SCC 中选一个点。

因为 source SCC 没有从外部进入的边，不选它就永远到不了。其他 SCC 都可以从某个 source SCC 沿 DAG 到达。

这就是“先压缩结构，再在 DAG 上解决”的典型思路。

DAG 上的 DP

DAG 没有环，所以天然有拓扑序。

很多 DAG 问题都可以按拓扑序做 DP：

目标递推形式
可达性$P[v] = \bigvee_{u\to v} P[u]$
路径计数$cnt[v] = \sum_{u\to v} cnt[u]$
最短路$dist[v] = \min_{u\to v}(dist[u]+w(u,v))$
最长路$dist[v] = \max_{u\to v}(dist[u]+w(u,v))$

DAG shortest path 可以处理负边权，因为没有负环，也没有任何环。

如果题目限制是 $O(m+n)$，而图又是 DAG，通常就是拓扑序 DP。

修改 relaxation：最宽路径

不是所有路径问题都是求权重和。

最宽路径（widest path）要求最大化路径上的最小边权。

定义：

$$ H[v] = \text{从 } s \text{ 到 } v \text{ 的路径中，最小边权能达到的最大值} $$

从 $u$ 走到 $v$，候选值是：

$$ \min(H[u], w(u,v)) $$

因为一条路径的宽度由最窄的边决定。

更新：

$$ H[v] = \max(H[v], \min(H[u], w(u,v))) $$

这和 Dijkstra 的结构很像，只是把“加法 + 取最小距离”换成了“取 min + 最大化瓶颈”。

高层上看，这是同一个 graph search 框架下换了路径代数。

Matching 和 Flow 的触发信号

如果问题是两类对象之间的一对一分配，先想到 bipartite matching。

典型结构：

  • 学生 vs 项目
  • 工人 vs 任务
  • 左侧位置 vs 右侧位置
  • 行 vs 列

如果每个对象有容量，或者一个人可以拿多个，matching 往往要升级成 flow。

判断时先问：

被配对的另一方，有没有自己的约束？

如果只是“物品不在乎谁拿”，可能是简单选择或 bipartite matching。

如果双方都有容量、互斥、费用、上下限，那更像 flow / min-cost flow。

图构造的心智模型

图建模的通用原则可以压成一句：

把“合法变化”变成边，把“当前必须记住的信息”变成节点。

如果一个信息会影响未来选择，它就应该进入状态。

如果一个信息只影响当前这一步的成本，它通常可以作为边权。

如果一个约束是“一次性资源”，比如 coupon，就用层数记录是否消耗。

如果一个约束是“路径全局属性”，比如颜色集合或 mod k，就把这个属性压成有限状态。

如果一个约束是“对象不能重复使用”，通常需要 matching、flow 或拆点。

图算法真正难的是这个编码过程。编码一旦正确，后面通常只是选择合适的黑盒算法。