差分约束与SPFA最长路：从糖果题掌握建图与正环判定

第一次做 SCOI2011 糖果这道题时我的第一反应是这题跟“差分约束”有什么关系n 个小朋友分糖果无非就是比较大小、算个数贪心排个序好像就完了。但仔细读题会发现约束条件不是一串连续的大小关系而是任意两个点之间五类关系混在一起有些还要求“严格小于”“严格大于”甚至直接给“等于”。这种问题要手推非常容易漏而差分约束正好就是处理任意变量之间线性不等式组的系统方法。这道题后来成了许多人的差分约束入门题因为它覆盖了最核心的三个点怎么把不等式变成图、求最值该跑最短路还是最长路、以及无解怎么判。这篇就按建图的完整流程来写从底层原理到能提交的代码再到我踩过的坑一次讲清楚。1. 这道题到底在考什么先读懂题意再谈建模先把题目里的信息全部列出来。题面给 n 个小朋友和 m 条要求每条要求是五种操作中的一种操作编号分别对应“A 和 B 一样多”“A 比 B 少”“A 不少于 B”“A 比 B 多”“A 不多于 B”。除了这五类约束外还有一个默认的硬条件每个小朋友都必须分到至少一颗糖。最后要求满足所有条件时糖果总数最少是多少如果条件本身互相矛盾就输出 -1。这种描述方式很像脑筋急转弯但其实每一条都在告诉你一个变量之间的不等关系。把它翻译成数学语言就顺多了。设第 i 个小朋友的糖果数为 x_i那么目标就是求一组非负整数 x_i使得所有约束成立并且让总和尽量小。1.1 五类条件速览输入操作文字含义数学表达1 A BA 和 B 一样多x_A x_B2 A BA 比 B 少x_B x_A 13 A BA 不少于 Bx_A x_B4 A BA 比 B 多x_A x_B 15 A BA 不多于 Bx_B x_A再加上 x_i 1问题就变成了一组带有下界约束的线性不等式组。注意操作 2 和操作 4 里的“1”不是随便来的两颗糖数量都是整数严格大于或者严格小于差值至少是 1。这个细节后面建图时会变成边权写错就直接 WA。1.2 为什么一眼看出是差分约束如果只有“A B”这种约束确实可以全部发 1 颗。一旦混入“A B”你就得让 B 拿 1、A 拿 2如果又有“B C”那 C 拿 1、B 拿 2、A 拿 3。这已经有点拓扑排序的感觉了。但题目里的约束不是链状而是网状甚至可能出现 A B、B A 这种互相矛盾的环。此时贪心顺序都定不了更别说手推答案。差分约束就是为解决这类问题设计的。把每个变量看成一个节点把每条不等式看成一条带权有向边问题就直接变成一个图论问题。糖果题的所有约束去掉常数后全是“”形式天然适合用最长路求解。所以它不是一道纯模拟题而是一道标准的差分约束板题。2. 差分约束的底层逻辑最短路还是最长路先想清楚很多初学者看到“差分约束”四个字就背模板结果遇到糖果这种求最小值的题就分不清该跑最短路还是最长路。这里值得花点时间把原理讲透。2.1 标准形式从不等式到有向边差分约束的标准形式一般是x_u x_v c对应到图里从 v 到 u 连一条权值为 c 的有向边然后跑最短路。为什么要从 v 连到 u因为最短路算法的松弛条件是if (dist[u] dist[v] c) dist[u] dist[v] c;你要更新的是 u而 u 的值由 v 和 c 推出来所以边的方向自然是从 v 指向 u。拿生活里的例子类比如果说“小明到达某个地点的时间不能晚于小红出发时间 5 分钟”你可以从小红的位置连一条权值 5 的边到小明跑最短路就是在求小明最早或最晚的可行时间。多条路径收敛下来最终每个点的 dist 就是满足所有上界约束的一个值。2.2 求最小值为什么要跑最长路糖果题的标准不等关系和上面正好相反是x_u x_v w对应松弛条件变成if (dist[u] dist[v] w) dist[u] dist[v] w;这就是最长路的松弛方式。现在最关键的问题来了题目要求糖果总数最少为什么不去跑最短路因为所有约束给出的都是下界而不是上界。比如 x_A 要大于等于 1还要大于等于 3那 A 的最小合法值就是 3也就是在所有下界里取最大值。最长路做的正是这件事从不同路径推出同一个点的多个下界然后取最大。举个例子。假设有两条路径路径一x_A x_C 2x_C x_B 3推出 x_A x_B 5路径二x_A x_D 4x_D x_B 1推出 x_A x_B 5。虽然两条路径结果一样但如果有第三条路径推出 x_A x_B 6那 A 的最小合法值就必须满足这个更紧的下界也就是取 max。最长路累加路径上的边权天然能把这个“取最大”的过程做掉。2.3 超级源点的作用把“至少一颗糖”写进图里差分约束本身没有起点所以需要人为加一个虚拟源点。最朴素的做法是建一个 0 号点从 0 到每个 i 连一条权值为 1 的边表示 x_i x_0 1其中 x_0 0。这样既保证图连通也把“每个小朋友至少一颗糖”这条约束塞进了图里。我在代码里用了另一个等价实现初始化时直接把所有点的 dist 设为 1并且全部入队。这样省去 n 条边效果和超级源点连权 1 的边完全一致。两种写法都行但要注意别漏掉“dist 初始为 1”这一步否则等于把题目里的硬条件丢了。3. 糖果题建模与建图方向、自环、边数三件事建模这一步直接决定对错。方向反了样例可能能过但一到大数据就会全盘崩掉。下面把五种操作的建图方式逐条列清楚给一个直接抄作业的表格。3.1 五类条件的图论翻译输入操作数学表达等价差分写法建边方式边权1 A Bx_A x_Bx_A x_Bx_B x_AA-BB-A02 A Bx_B x_A 1x_B x_A 1A-B13 A Bx_A x_Bx_A x_B 0B-A04 A Bx_A x_B 1x_A x_B 1B-A15 A Bx_B x_Ax_B x_A 0A-B0建图方向有个统一口诀把不等式写成“左侧变量 右侧变量 权值”边一定从右侧变量出发指向左侧变量。举两个最容易混的例子输入 4 A B意思是 A 的糖比 B 多。改写为 x_A x_B 1右侧变量是 B所以建边 B-A权值 1。输入 5 A B意思是 A 不多于 B。改写为 x_B x_A 0右侧变量是 A所以建边 A-B权值 0。很多题解把这个过程反着写一样能跑出答案因为你只要把整张图的方向同时反过来在无环情况下结果往往还是对的。但一旦出现环方向反了很容易让判环逻辑跟着乱。我强烈建议每次建图前先在草稿纸上写一次不等式别直接背边表。3.2 自环、0 权边与正环的边界操作 2 和操作 4 如果出现 a b也就是“自己比自己少”或“自己比自己多”那么 x_a x_a 1 直接矛盾。这种无解可以在输入时立刻判掉比让 SPFA 慢慢找正环快得多也更稳。0 权边本身不会产生正环。操作 1 在 A、B 间建两条 0 权边这表示等价关系。两个节点之间来回 0 权边只是让它们相等最长路遇到 0 权环时 dist 不会变大所以没有持续松弛的驱动力。看到双向 0 边不必担心死循环。真正无解的标志是正环也就是环上边权之和严格大于 0。比如 A B 1B A 1两条边把两个点串成一个环沿环累加得到 0 2 的矛盾。在最长路里正环会让 dist 无限增大算法停不下来。所以判无解本质上就是判正环。3.3 边数、数组大小与复杂度n 和 m 都是 1e5 级别边数不能按 m 直接算。最坏情况是所有条件都是操作 1每个条件建两条 0 权边共 2m 条如果用超级源点写法还要再往每个节点连一条边也就是 n 条总共最多 3e5 条边。代码里 MAXM 开到 400005留足余量。节点数方面MAXN 开到 100005。虽然这题如果采用全点初始入队写法用不到 0 号点但多开 5 个是防御性编程防止数组越界把 head 改坏。复杂度上建图是 O(nm)SPFA 跑最长路平均接近 O(km)k 是小常数最坏 O(nm) 在理论上是存在的但这题的数据范围就是按 SPFA 能过设计的。只要方向、判环、数据范围这几处不写错正常能过。4. 核心实现SPFA 最长路与正环判定的完整代码图建完之后剩下的事就是跑最长路和判正环。这里有两个常见争议点一是队列初始化怎么写二是正环判定用入队次数还是路径边数。4.1 判定正环的正确姿势网上很多 SPFA 判负环的模板是记录每个节点的入队次数一旦某个节点入队超过 n 次就认为有环。这种写法在普通负环题里很常见但在糖果这种带大量 0 权边的图上不够放心。0 权双向边可能让一个节点反复入队但并没有真正的正环。更严谨的做法是维护 cnt[v]表示当前到 v 的最长路由多少条边组成。每次松弛成功时更新cnt[v] cnt[u] 1;如果某个 cnt[v] n说明存在一条路径经过了至少 n 条边。无环路径只有 n 个点最多 n-1 条边n 条边必然意味着有节点被重复经过也就是存在环而且这条环还能继续让 dist 变大说明是正环无解。这个判断等价于 Bellman-Ford 做 n 轮之后仍然能继续松弛比单纯数入队次数更贴近问题本质也更不容易误判。4.2 完整可运行代码下面是完整的 C17 实现使用链式前向星存图队列实现 SPFA 最长路。#include bits/stdc.h using namespace std; const int MAXN 100005; const int MAXM 400005; struct Edge { int to, w, nxt; } edges[MAXM]; int head[MAXN], tot; int n, m; long long dist[MAXN]; int cnt[MAXN]; bool inq[MAXN]; void addEdge(int u, int v, int w) { edges[tot] {v, w, head[u]}; head[u] tot; } bool spfa() { queueint q; // 每个小朋友至少一颗糖等价于超级源点连权 1 的边 // 这里直接初始化 dist 1并把所有点入队 for (int i 1; i n; i) { dist[i] 1; q.push(i); inq[i] true; } while (!q.empty()) { int u q.front(); q.pop(); inq[u] false; for (int e head[u]; e; e edges[e].nxt) { int v edges[e].to; int w edges[e].w; if (dist[v] dist[u] w) { dist[v] dist[u] w; cnt[v] cnt[u] 1; if (cnt[v] n) return false; // 存在正环 if (!inq[v]) { q.push(v); inq[v] true; } } } } return true; } int main() { scanf(%d%d, n, m); int opt, a, b; for (int i 0; i m; i) { scanf(%d%d%d, opt, a, b); if (opt 1) { addEdge(a, b, 0); addEdge(b, a, 0); } else if (opt 2) { if (a b) { puts(-1); return 0; } addEdge(a, b, 1); // x_b x_a 1 } else if (opt 3) { addEdge(b, a, 0); // x_a x_b 0 } else if (opt 4) { if (a b) { puts(-1); return 0; } addEdge(b, a, 1); // x_a x_b 1 } else { addEdge(a, b, 0); // x_b x_a 0 } } if (!spfa()) { puts(-1); return 0; } long long ans 0; for (int i 1; i n; i) ans dist[i]; printf(%lld\n, ans); return 0; }代码里的head数组默认是 0所以链式前向星用for (int e head[u]; e; e edges[e].nxt)遍历不需要初始化成 -1也不需要写终止条件e ! -1。这是个省事的写法但如果你改了初始化方式循环条件也要跟着改。4.3 代码里几个“省心”的处理第一自环特判放在输入循环里。操作 2 或操作 4 遇到 a b直接输出 -1 返回不用把这种明显矛盾的数据丢给 SPFA 判正环。这个优化对某些极端数据很有用。第二所有点初始 dist 1 并全部入队。这是把超级源点省掉了。如果你选择传统的 0 号点超级源点写法记得从 0 到每个 i 连权 1 的边并且只把 0 号点先入队dist[i] 初始是 0等 0 号点弹出后更新为 1。两种写法的结果一样但混着用会出问题。第三cnt[v] 的更新必须发生在“松弛成功”时而不是节点入队时。有些写法把cnt[v]写在入队判断里那样统计的是入队次数语义就变了。顺手写在松弛分支里配合cnt[u] 1才是路径边数。第四答案要用 long long。极端链状约束下一个人最多可能拿到 n 颗糖总和能达到 n(n1)/2 的量级n 1e5 时大约是 5e9远超 int 范围。5. 五分钟自查常见问题与调试技巧实录最后这部分是实战里最容易踩的坑也是我 debug 时最常遇见的几类问题。如果你写完代码卡住了按这个顺序检查一遍多半能定位。5.1 方向反了样例能过但 OJ 全 WA建图方向反了最常见的症状是样例能过但随机造几个数据答案偏小或者把合法数据判成 -1。因为最长路沿着错误方向传播时下界根本传递不出去dist 停留在初始值。给几个适合自查的小数据输入手算答案n2, m1, 操作4 1 23x12, x21n2, m1, 操作2 1 23x11, x22n2, m2, 操作2 1 2操作4 2 1-1互相矛盾n3, m2, 操作4 1 2操作4 2 36x13, x22, x31如果第一组数据输出 2说明操作 4 的建边方向有问题如果输出 4说明你可能在建正确边的同时又多建了一条反向 0 权边。严格大于和严格小于这类约束边权写成 0 而不是 1也会导致答案比预期小 1。5.2 TLE、死循环与不严谨的判环提交 TLE 时第一反应不要是换算法先检查链式前向星的数组够不够大。数组越界会导致 head 数组被写入的边覆盖SPFA 遍历到野生边出现随机跳边复杂度直接爆炸甚至死循环。MAXM 按 3e5 算但实际开 4e5就是为了防这种边界情况。死循环第二排查点是判环逻辑。如果你用的是“入队次数超过 n”的写法在 0 权边多的图里可能误判如果用的是 cnt 路径长度但把更新时机写错了比如在入队时cnt[v]也会误判。标准写法是上面代码里那种只写在松弛成功之后。如果数据确实卡 SPFA可以尝试用 deque 做 SLF 优化。最长路的 SLF 原则是如果新节点的 dist 比队首节点的 dist 大就把新节点放到队首否则放到队尾。本质是让较大下界先参与松弛减少无效更新。但这个优化不是所有题目都能显著提速属于可加可不加的调优。另外说一句有些人喜欢用栈代替队列来跑 SPFA 判环理由是负环/正环在栈实现下收敛快。实测下来栈在处理某些环状退化数据时确实快但稳定性不如队列而且如果你没把 DFS 版 SPFA 的访问状态写对很容易出现漏判。除非你非常清楚自己在干什么否则不推荐在比赛里临时换栈。5.3 答案溢出与初始化陷阱int 溢出藏得很深。极端情况下一条 1 2 3 ... n 的链最大的小朋友拿 n 颗总和能到 5e9 量级。如果你用 int 累加结果可能变成负数OJ 上表现为奇怪的大数或者 -1。这不是算法错是类型错。初始化方面求最长路时 dist 的初值必须体现“每个小朋友至少一颗糖”这条件。代码里直接设 dist[i] 1 是最直观的。如果你选择超级源点 0 号点写法dist 初值可以全为 0因为 0 号点连向每个点的边权是 1第一次松弛就会把 dist[i] 更新成 1但如果你又把 dist[i] 预先设成 1同时又从 0 号点连权 1 的边不会把答案算大因为从 0 推来的值还是 1这个细节不算错只是逻辑绕。还有 memset 的问题。这题只有一组数据静态数组默认就是 0不需要清空。但如果你的代码被放在多组数据的框架里测试记得重置 tot 和 head。链式前向星如果用的 0 作为空指针head 重置为 0 即可如果用 -1addEdge 里的 nxt 和循环终止条件都要改成e ! -1别混用。写在最后的个人习惯最后分享一个我做差分约束题的小习惯拿到题目先不急着写代码把所有条件按“x_u x_v w”的格式重写一遍然后对每条边检查“右侧变量是谁就从谁出发指向左侧变量”。这个动作花不了两分钟但能避免大部分建图错误。糖果这道题做完之后你可以把它变形着玩把操作 2 和 4 改成普通的“小于等于”“大于等于”把“至少一颗糖”改成“至少 k 颗糖”或者把两个点之间的约束换成区间前缀和的形式。核心套路还是同一套差分约束、图建模、最短路或最长路、判环。把这道题吃透后面遇到区间覆盖、排班限制、前缀和约束这类问题你会有种“不过是换了个壳”的感觉。