刷过 SCOI2011 这道“糖果”的人十有八九是从“差分约束”这四个字开始怀疑人生的。题面看起来像模拟题数据范围看起来像图论题最后发现它是一道用 SPFA 跑最长路的经典题——或者说是一道把五条生日规则翻译成不等式的翻译题。我第一次做的时候样例一遍过交上去却迎来一个大大的 WA后来排查半天发现是 A 和 B 的建图方向翻了从那以后我对这种不等号上下文的敏感度提升了一个档次。这篇文章我不想讲什么高深的东西就按我自己的踩坑顺序把题意翻译、差分约束原理、建图细节、SPFA 实现、正环判断以及一个更稳的 Tarjan 缩点做法都梳理一遍。无论你是刚接触差分约束的新手还是刷题卡了很久想换思路的选手应该都能从里面捞到点有用的东西。1. 题目在问什么先把规则翻译成不等式1.1 五种规则分别是啥意思原题是幼儿园分糖果N 个小朋友K 条要求每条要求用 1 到 5 五个编号之一给出形式都是“A 和 B 之间怎么样”。设第 i 个小朋友手里的糖果数量为 x[i]题目最终要求满足所有要求时糖果总数的最小值如果要求本身矛盾就输出 -1。五种规则翻译成不等式是这样的规则编号原话含义等价不等式建出来的边1A 和 B 一样多x[A] x[B] 且 x[B] x[A]B - A 权 0A - B 权 02A 比 B 少x[B] x[A] 1A - B 权 13A 不少于 Bx[A] x[B] 0B - A 权 04A 比 B 多x[A] x[B] 1B - A 权 15A 不多于 Bx[B] x[A] 0A - B 权 0这里最容易写错的是 2 和 4。规则 2 说“A 比 B 少”也就是 B 比 A 多B 的糖果数至少是 A 的糖果数加 1所以是 B A 1边从 A 指向 B。规则 4 反过来A 比 B 多所以 A B 1边从 B 指向 A。很多人第一次做会把边方向完全建反然后样例都过不了。1.2 一个容易被忽略的隐藏约束题目没明说但是每个小朋友至少要分到 1 颗糖果。这个条件也要建模进去。一般的做法是加一个超级源点 0令 x[0] 0然后从 0 向每个小朋友 i 连一条权值为 1 的边表示 x[i] x[0] 1也就是 x[i] 1。这个超级源点还有个额外好处它让整张图从 0 出发能到达所有点图变成连通的了。后面跑 SPFA 的时候只需要从 0 做单源最长路不需要初始化时把每个点都塞进队列非常省事。2. 差分约束和图的最长路原理与直觉2.1 从不等式到图的固定套路差分约束系统的本质是一堆形如 x[v] x[u] w 的不等式。每个不等式都可以理解为如果 u 的值确定了那么 v 的值至少要达到 u w。这和图论里的“边”天然吻合——从 u 到 v 连一条权值为 w 的有向边然后跑最长路得到的 dist[v] 就是满足所有这类约束时v 能取到的最紧下界。为什么是最紧下界你想象一下如果存在一条路径 u0 - u1 - u2 - ... - uk那么沿着路径累加会得到 x[uk] x[u0] (w1 w2 ... wk)。路径越长、边权和越大对终点的约束就越强。一个点可能有好多条路径到达这些路径给出的下界里肯定要取最大的那个才不会被任何一条限制条件打破。这正好就是最长路做的事不断用 dist[u] w 去更新 dist[v]只保留更大的值。2.2 求最小值为什么反而跑最长路很多人一开始想不通题目求的是糖果总数最小值怎么反而用最长路关键点在于我们建的每条边都是一个下界约束。比如“B 比 A 多 1”这条约束本质是在说“B 的取值不能小于 A1”。所有约束累加起来会让每个变量的可行域有一个下限。为了满足所有约束每个变量实际取值只要不低于这个下限就行。那为了让总和最小自然应该让每个变量都恰好取到自己的下限。这里的哲学就是对于 x[v] x[u] w 这种不等式系统求一组满足约束的可行解并且让目标函数总和最小等价于求每个变量在约束下的最大下界。最大下界就是通过最长路算出来的。同理如果题干给的是 x[v] x[u] w 这种上界约束求最大值就要用最短路。2.3 正环为什么代表无解最长路里最怕出现正权环。如果图里有一个环环上的边权之和大于 0那沿着这个环绕一圈就能得到一个更大的下界再绕一圈又更大绕无限圈下界就趋向正无穷。也就是说这个约束系统里不存在有限值能满足所有条件原题输出 -1。注意边权和恰好等于 0 的环不会产生矛盾它只会让环上所有点的取值相等这是正常现象。比如规则 1 建立的两条权 0 双向边就是让 A 和 B 相等不构成无解。生活里可以这么类比你答应朋友“我至少比你多 1 块钱”朋友又答应你“我至少比你多 1 块钱”。这两个承诺同时存在就形成了一个正环谁也拿不出那么多钱。差分约束的正环就是这种逻辑矛盾。3. 建图细节与代码实现3.1 核心建图清单先把所有规则整理成一张建图清单我每次写代码前都会在草稿纸上列一遍这个表避免方向写反规则 1A B建两条权 0 边A - BB - A规则 2A B即 B A 1建 A - B 权 1规则 3A B即 A B 0建 B - A 权 0规则 4A B即 A B 1建 B - A 权 1规则 5A B即 B A 0建 A - B 权 0再叠加超级源点 0 到所有点的权 1 边。全部加完后这张图里边的数量是 K 条原始规则对应的边规则 1 产生两条再加上 N 条源点边完全放得下。3.2 超级源点的一点点经验0 - i 这条权 1 的边非常关键新手容易漏掉。漏掉之后每个孩子的下限就是 0答案是 0错得离谱。还有些人喜欢把所有点初始化成 1 然后全部入队效果上等价但我不推荐原因有二一是初始化成 1 再入队无法严格表达“从源点出发最长路”这个模型判断正环时容易出歧义二是统一加超级源点代码结构更整洁后续如果题目改成“每人至少分 5 颗”只需要把权值改成 5不用动别的地方。3.3 SPFA 完整代码下面这份代码我加了 SLF 优化也就是 Small Label First用双端队列实现。虽然 SPFA 理论上会被卡但在这道题的数据范围下SPFA 加 SLF 通常能稳定通过。N 最大 100000K 最大 100000用 vector 存边没问题。#include bits/stdc.h using namespace std; const int MAXN 100005; const long long INF 0x3f3f3f3f3f3f3f3fLL; struct Edge { int to, w; }; int N, K; vectorEdge G[MAXN]; long long dist[MAXN]; int cnt[MAXN]; bool inq[MAXN]; bool spfa() { memset(dist, -INF, sizeof(dist)); dequeint q; dist[0] 0; q.push_back(0); inq[0] true; while (!q.empty()) { int u q.front(); q.pop_front(); inq[u] false; for (const Edge e : G[u]) { int v e.to; int w e.w; if (dist[v] dist[u] w) { dist[v] dist[u] w; if (!inq[v]) { inq[v] true; cnt[v]; // 正常图里最多 N1 个点超过这个入队次数说明存在正环 if (cnt[v] N 2) return false; // SLF 优化比队首的 dist 还大就插到前面 if (!q.empty() dist[v] dist[q.front()]) q.push_front(v); else q.push_back(v); } } } } return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin N K; for (int i 0; i K; i) { int op, A, B; cin op A B; if (op 1) { G[A].push_back({B, 0}); G[B].push_back({A, 0}); } else if (op 2) { G[A].push_back({B, 1}); } else if (op 3) { G[B].push_back({A, 0}); } else if (op 4) { G[B].push_back({A, 1}); } else { G[A].push_back({B, 0}); } } for (int i 1; i N; i) { G[0].push_back({i, 1}); } if (!spfa()) { cout -1 \n; return 0; } long long ans 0; for (int i 1; i N; i) { ans dist[i]; } cout ans \n; return 0; }代码里有两个细节值得说明。第一个是判环条件我写的是cnt[v] N 2因为整张图包含 0 号点在内共 N1 个点SPFA 中一个点的入队次数如果超过总点数基本可以断定存在正环。第二个是 ans 用了 long longdist 也用了 long long因为 N 最大 100000每人最少 1 颗最优答案本身可能只有 100000但是中间路径长度累加时有可能超出 int 范围用 long long 比较省心。4. 常见翻车现场与排查速查4.1 症状对照表做题时遇到的奇怪问题多半是下面几个原因之一。我把症状和解决方案整理成了一张表症状可能原因解决办法样例输出 0忘了加 0 - i 的权 1 边每个点至少 1 颗糖源点边不能省小数据对大数据 WA答案溢出 intdist 和 ans 全部用 long long第一个样例就错规则 2 和 4 的边方向反了先写成 x[v] x[u] w再按 u - v 加边输出 -1 但手算可行判环条件太宽松检查入队次数阈值或者改用入队次数加深搜验证超时SPFA 被卡加 SLF/LLL 优化或换 Tarjan 缩点做法递归爆栈用递归 DFS 求最长路改成队列 SPFA避免递归4.2 自环要提前特判吗有几种情况会直接形成自环正权边。比如输入2 A A意思是 A 比 A 少显然矛盾建出来的边是 A - A 权 1SPFA 跑起来之后这个自环会让 A 无限变大连环都出不来。输入4 A A同理。这种数据其实不需要特判因为 SPFA 遇到自环正权边也会因为点数限制认定存在正环输出 -1。不过如果你想提前优化可以在读入时直接判断if ((op 2 || op 4) A B) { cout -1 \n; return 0; }这样能省掉一些不必要的建图开销。规则 1、3、5 出现 A B 时不会产生矛盾比如1 A A自己等于自己直接忽略即可。4.3 SPFA 被卡的时候还能怎么救SPFA 在构造数据下退化成 O(N*M) 是很有可能的。除了代码里的 SLF还可以试试 LLL 优化也就是把队首元素拿出来后如果它的 dist 大于队列内所有元素的平均值就放到队尾再处理。不过 LLL 的代码比 SLF 稍麻烦而且在某些数据下效果不稳定。更实用的一个做法是如果发现 dist[v] 要被更新成一个超过理论上限的值可以直接判无解退出。外层设置一个上限比如所有 dist 之和明显超过题目答案范围时说明已经出现正环。但这属于 hack 式写法不够规范。我后面会讲 Tarjan 缩点做法那才是真正稳定的路线。5. 更稳的路线缩点 DAG 上 DP5.1 为什么能想到缩点观察整张图的边权只有 0 和 1 两种。如果存在一个正环环上一定至少有一条权 1 的边加上若干权 0 的边。反过来想如果图里所有环的边权和都是 0那就说明没有任何矛盾。更妙的是如果两个点在同一个强连通分量里那么它们之间一定互相可达。由于边权只有 0 和 1要保证环路权总和非负无矛盾同一个 SCC 内部所有边权都必须为 0。换句话说同一个 SCC 里的所有小朋友在最优解里必须拿一样多的糖果。这样可以把整个 SCC 缩成一个点然后在缩点后的 DAG 上算最长链。5.2 关键代码Tarjan 求 SCC 是标准模板我不把完整代码贴出来了只写缩点后的核心逻辑。// 假设 tarjan 已经跑完 // belong[i] 表示节点 i 属于哪个 SCC // sccCnt 表示 SCC 总数 // 原图边存在 G[u] 里每个元素是 {to, w} vectorpairint, int dag[MAXN]; bool hasPositiveRing false; for (int u 0; u N; u) { for (auto e : G[u]) { int v e.to; if (belong[u] ! belong[v]) { dag[belong[u]].push_back({belong[v], e.w}); } else if (e.w 1) { // 同一个 SCC 内有边权为 1 的边说明存在正环 hasPositiveRing true; } } } if (hasPositiveRing) { cout -1 \n; return 0; } // Tarjan 的 SCC 编号从大到小遍历正好是 DAG 的拓扑序 vectorlong long dp(sccCnt 1, -INF); dp[belong[0]] 0; for (int id sccCnt; id 1; id--) { if (dp[id] -INF) continue; for (auto e : dag[id]) { int v e.first; int w e.second; dp[v] max(dp[v], dp[id] w); } } long long ans 0; for (int i 1; i N; i) { ans dp[belong[i]]; } cout ans \n;这段代码的关键是最后那个循环Tarjan 算出的 SCC 编号越大在 DAG 中越靠前所以从大到小遍历就相当于拓扑排序。不需要再写队列拓扑非常简洁。5.3 两种做法怎么选如果你只是为了快速 ACSPFA 加 SLF 是最省脑子的方案代码量小写起来快。如果你追求的是稳定性或者你所在的题库里 SPFA 被卡得厉害那就用 Tarjan 缩点。两种做法的时间复杂度差距也明显SPFA 最坏 O(N*K)Tarjan 加 DP 是稳定的 O(NK)。我自己日常刷题的习惯是先用 SPFA 过思路如果时间特别紧或者数据特别强再切换到缩点做法。这道题最值得学的地方不是背 SPFA 模板而是理解“边权只有 0/1”这个特殊性质它让缩点做法变得可行。以后遇到类似的差分约束题先看看边权是不是只有两种如果是优先考虑 SCC DAG DP这是很多竞赛选手不会明说的技巧。最后再分享一个我自己养成的习惯动手建图前先把所有规则在草稿纸上翻译成x[v] x[u] w的统一格式再机械地加边。这个流程看起来笨但能避免 90% 的方向错误。等你熟练了会发现差分约束题的核心永远不是 SPFA 或者 Tarjan而是把自然语言描述的约束条件正确无误地变成一条条有向边。方向对了剩下的只是套模板而已。