第一次在OJ上看到“糖果”这道题时我差点以为是个贪心或模拟题。结果点开题面看到五种约束条件再看到“差分约束”四个字出现在标题里心里大概就有数了——这是一道把差分约束系统几乎全部核心考点都串起来的题。网上不少人都说它是一道“模板题”但真正动手写过一遍就会发现模板只是起点难的是建模方向、正环判定和边界处理。这道题来自某省省选SCOI2011题面大意是有n个小朋友分糖果给出k条约束关系要求满足所有约束的前提下求最少需要准备多少颗糖。约束一共有五种类型正好覆盖了差分约束里最常见的等量、严格小、非严格小、严格大、非严格大关系。我当年刷这道题时踩了不少坑今天把完整的建模思路、代码实现和排错经验一次写清楚希望对正在刷差分约束的你有帮助。1. 糖果分配问题的约束本质这题究竟在考什么1.1 题面约束类型的整体梳理题目给你n个小朋友和k条要求每条要求形如“x A B”x的范围是1到5含义分别是x1小朋友A和B的糖果一样多x2A的糖果比B少x3A的糖果不少于Bx4A的糖果比B多x5A的糖果不多于B最终要求的是满足这k条约束的前提下糖果总数的最小值并且每个小朋友至少要有1颗糖。从数学形式上看这些约束全部可以写成“A和B之间的差值满足某个不等号”的形式而这正是差分约束系统的定义。差分约束系统本质上就是把一组形如x_u - x_v c或x_u - x_v c的不等式转化为图上的最短路或最长路问题来求解。1.2 为什么这道题适合作为差分约束的入门题我见过很多讲差分约束的教程大多是从理论到理论读者看完依然不知道具体题目怎么下手。而这道题的好处在于五种约束刚好把差分约束的几种常见变形都覆盖了等量关系需要拆成两条不等式严格不等关系需要考虑“差至少为1”的整数条件非严格不等关系直接转为差为0的不等式每人至少1颗糖需要一个虚拟源点来兜底理解了这道题的建模基本上也就掌握了差分约束在实际题目里的思考套路。接下来从最底层的原理讲起先搞明白为什么“不等式组”能变成“图上的最长路”。这部分的逻辑如果不透彻后面写代码时很容易把建边的方向搞反。2. 差分约束与最长路的对应关系从不等式到图的底层思路2.1 最短路三角不等式与最长路的对称关系如果读者之前接触过最短路一定知道松弛操作的核心依据是这个不等式dist[v] dist[u] w(u, v)也就是说如果从u到v有一条权值为w的边那么在任意一组最短路的距离中dist[v] - dist[u]不会超过w。把上面的不等式稍作变形就得到了dist[v] - dist[u] w这就是一个差分约束的标准形式。假设现在有一个变量组x_1, x_2, ..., x_n以及一些形如x_v - x_u c的约束我们就可以从u向v连一条权值为c的有向边然后跑最短路。跑完后dist数组就是满足所有约束的一组可行解。反过来如果把松弛条件写成dist[v] dist[u] w(u, v)那就变成了最长路问题。对应的不等式是dist[v] - dist[u] w这正是本题需要的核心形式因为在“糖果”这道题里几乎所有约束都在说“A比B多或者不少于某个值”用大于等于号来表达是最自然的。2.2 约束方向与建边方向最容易搞混的环节很多新手会在这里犯迷糊不等式明明是x_v - x_u c为什么建边是从u到v而不是从v到u这里的关键在于理解最长路松弛操作的方向。跑最长路时如果从u出发能走到v我们就会尝试用dist[u] w去更新dist[v]。如果更新成功意味着得到了一个更大的、仍然受约束限制的可行值。所以不等式中“被减数”对应的变量这里是v应该是边的终点“减数”对应的变量这里是u是边的起点。换一种说法x_v - x_u c的意思就是“v至少要比u大c”那么在图上就是u指向v权重为c这样从源点出发沿着边方向累加权重dist值才会随着路径方向递增最终满足所有约束。我一开始学的时候总会把方向搞反后来用了一个非常朴素的记忆方式把不等式写成被减数 减数 c然后“被减数”在前面就把边指向被减数。这句话虽然不严谨但做题时特别好用。2.3 正环、负环与解的存在性最短路问题里如果图中存在负环那么dist会被无限松弛下去因为每次绕一圈都能让距离变得更小所以不存在有限的最短路。差分约束系统对应地也没有可行解。最长路问题对称地存在“正环”的概念如果图中存在一个环且环上边权之和为正那么每绕一圈dist就能变得更大永远无法收敛同样的约束系统无解。在“糖果”这道题里无解情况其实很好构造。比如有两条约束A比B多x_A - x_B 1和B比A多x_B - x_A 1。这两条不等式同时成立意味着x_A x_B同时x_B x_A矛盾。反映到图上就是A指向B的权1边和B指向A的权1边形成了一个总权值为2的正环。这里有个细节0权边组成的环会不会导致无解答案是不会。0权环的环权总和是0跑最长路时绕一圈并不会让dist增加SPFA可以正常收敛。所以判断无解的唯一依据是“是否存在正环”。3. 五种约束条件的建模拆解每条边为什么这样连3.1 x1等量关系要拆成两条有向边x1给出的条件是A和B一样多也就是x_A x_B。一个等号在差分约束里要拆成两个方向的不等式x_A - x_B 0x_B - x_A 0建边时就是B指向A的权0边再加上A指向B的权0边。两条0权边构成一个0权环不影响答案的正确性只是增加了一些边数。有人可能会问等量关系能不能用一条“双向权0边”来表示在逻辑上等价但用代码实现时还是要写两条有向边。如果用的是邻接表哪怕不额外分方向存储上也是需要两条边记录的。我一般会老老实实add两次避免后续判断方向时给自己挖坑。3.2 x2严格小于要变成“差至少为1”x2表示A的糖果比B少也就是x_A x_B。因为糖果数量必须是整数“小于”就意味着至少差1。所以不等式写成x_B - x_A 1建边方式是A指向B边权为1。这道题里所有严格不等关系都要注意这个“整数1”的处理。差分约束处理的是实数变量时“严格小于”并不能直接转化为整数差1但在这类糖果分配、排名、时间安排等整数场景里“至少相差1”是唯一合理的转化方式。3.3 x3和x5非严格约束直接转成0权边x3表示A的糖果不少于B即x_A x_B写成x_A - x_B 0建边B指向A权0。x5表示A的糖果不多于B即x_A x_B等价于x_B - x_A 0建边A指向B权0。我把x3和x5放在一起说是因为它们本质上是同一个关系换了主语建边时只要先判断“谁是被减数”再从减数指向被减数即可。这两个条件都是0权边也都不参与正环的构成纯粹是限制性的约束。3.4 x4严格大于与x2形成对称x4表示A的糖果比B多即x_A x_B整数化后x_A - x_B 1建边B指向A权1。可以看到x4和x2是完全对称的操作唯一的区别是谁指向谁。很多时候建边错误就出现在这种对称关系上所以我在写代码时会习惯性注释一行“被减数指向减数”防止自己对着题目发呆。3.5 每人至少1颗糖虚拟源点的关键作用题面里还有一个容易被忽略的隐含条件每个小朋友至少要分到1颗糖。这个条件如果不处理跑出来的dist很可能全是0答案就会是0显然不符合要求。处理方法有几种。比较直接的一种是建立一个虚拟源点0从0向每个小朋友连一条权值为1的边对应不等式x_i - x_0 1然后令虚拟源点的dist为0跑最长路。这样每个小朋友的dist都至少会被这个源点更新成1正好满足“每人至少1颗糖”的条件。这里有一个更深处的问题为什么不把dist初始值直接设为1理论上可以但这意味着你手动预设了一组初始可行解。如果后续约束中出现矛盾你需要依赖正环检测来发现无解。用虚拟源点的方式则把“满足每个变量至少有下界”这件事也统一成了图上的最长路问题思路更加一致也不容易漏初始化。4. 超级源点与正环判断全题最容易翻车的两个设计点4.1 两种超级源点建法统一入队还是预先赋值虚拟源点的具体实现方式会直接影响SPFA的起点设置。我见到过两种常见写法方法A建立节点0向每个1到n的节点连边权为1的边然后把节点0入队dist[0]0跑一次完整的最长路。方法B把每个dist[i]初始化为1然后把所有节点都入队相当于虚拟源点向每个节点连边后立刻完成第一轮松弛。方法B是不少人的首选因为它省掉了n条建边代码上快一点。但问题也很微妙如果某个约束链比较长比如“A至少比B多3B至少比C多5”那么dist在BFS式的SPFA中需要多轮松弛才能传导到位。假如入队顺序不佳中间某个节点的dist值被反复调整效率会下降甚至卡到超时。方法A看起来多建了n条边但这n条边的存在反而让“初始上界”从源点开始逐层传播SPFA的处理顺序更接近拓扑展开实际运行中往往更稳。我最终用的是方法A调试起来也直观dist[0]0是唯一的初始状态不加任何特殊处理。4.2 SPFA判断正环时最容易误判的地方SPFA判负环的经典做法是统计每个节点的入队次数一旦某个节点入队次数超过n就判定存在负环。这个方法搬到最长路上也一样但有几个坑第一入队次数统计的时机。如果仅仅在“成功松弛”时才让cnt加1但同一个节点可能在已经入队的情况下又被多次尝试松弛那么cnt并不能准确反映路径上的环。正确做法是只有在dist[v] dist[u] w最长路成功更新并且v当前不在队列中时才把v入队同时cnt[v]加1。如果v已经在队列里只需要更新dist不必重复入队。第二正环可能不在源点所在的连通分量里。这句话的意思是说如果虚拟源点0不能到达某个负权环所在的子图那SPFA从源点出发永远找不到这个环。但在这道题里虚拟源点0向每个点都连了边所以从0出发能到达所有点任何正环都会被扫描到。这个设计反过来也说明不要为了省n条边而使用方法B却不把所有点初始入队那样一旦出现孤立子图的正环就会漏判最终得到一个错误答案而不是“无解”的提示。第三用cnt[v] n还是cnt[v] n我习惯用 n 1或者等价的“某个节点进队超过n次就判定有环”。这个细节其实不关键关键是cnt统计的起点是从源点出发经过的节点数而不是松弛次数。有时负环很小只有两个节点但跑SPFA时由于0权边很多节点可能会入队很多次看起来非常接近n但并没有真正成环。所以不少选手会选择把阈值放宽一点比如统计“从源点到该节点最长路径上的边数”如果超过n就判定有环这样在逻辑上更自然也没怎么听说过误判的情况。4.3 为什么零权边也会成为卡时间的元凶SPFA的复杂度在最坏情况下是O(nm)这不是理论上的恐吓而是真的有出题人会构造专门的数据来卡。零权边在“糖果”这道题里无处不在等量关系、不少于、不多于都会产生零权边。当大量零权边形成一条很长的链时SPFA的松弛顺序可能非常糟糕跑出接近最坏复杂度。优化手段可以有几个方向使用双端队列在松弛成功时按一定策略判断从队首还是队尾插入或者在队列为空时优先取出队首的节点。我个人的实测感受是对于本题随数据分布不同SLF优化偶尔有效但不是银弹。更稳妥的做法是把判环条件细化尽早发现正环从而提前退出而不是一直跑到超时。5. 完整代码实现与关键函数的逐段注释5.1 链式前向星建图与数据结构下面给出我调试通过的核心代码。为了效率我用链式前向星存图因为本题边数上限大约有k n条全部用vector存也能过但链式前向星在遍历邻接边时少一些开销。#include bits/stdc.h using namespace std; const int MAXN 100005; const int MAXM 200005; struct Edge { int to, w, next; } edges[MAXM]; int head[MAXN], tot; int dist[MAXN], cnt[MAXN]; bool inQueue[MAXN]; int n, k; void addEdge(int u, int v, int w) { edges[tot].to v; edges[tot].w w; edges[tot].next head[u]; head[u] tot; } void initGraph() { memset(head, 0, sizeof(head)); tot 0; for (int i 1; i n; i) { addEdge(0, i, 1); } }这里的initGraph一次性处理了虚拟源点向每个小朋友连权1边的操作。要注意addEdge(0, i, 1)的方向源点指向小朋友说明是小朋友的糖果数至少比源点大1。5.2 SPFA最长路主逻辑与正环检测SPFA主函数的核心就是松弛和判环。我单独抽出来写方便对照说明。bool spfa() { queueint q; memset(dist, -0x3f, sizeof(dist)); dist[0] 0; q.push(0); inQueue[0] true; while (!q.empty()) { int u q.front(); q.pop(); inQueue[u] false; for (int i head[u]; i; i edges[i].next) { int v edges[i].to; int w edges[i].w; if (dist[v] dist[u] w) { dist[v] dist[u] w; cnt[v] cnt[u] 1; if (cnt[v] n) { return false; } if (!inQueue[v]) { q.push(v); inQueue[v] true; } } } } return true; }这段代码里有几个地方值得仔细看dist的初始值设为一个很小的负数确保第一次松弛一定会成功因为所有边权都非负源点出发的权1边会把dist[1..n]更新为1。如果把dist初始化为0理论上结果可能也没错因为所有实际值都为正但“每个点至少1”这个条件的表达就会变得不那么干净而且对于某些变量的下界大于1的情况初始化0依然能正常工作但逻辑上不够统一。cnt[v] cnt[u] 1这行是我推荐的做法统计最长路路径上的“边数”。如果某个节点到源点的最长路径边数超过了n说明一定走了重复节点也就是出现了正环。这个定义比单纯的进队次数更接近正环的数学本质也不容易误判。5.3 读入五种约束并建边主函数里的读入部分按五种类型分别建边。我加了注释帮助理解方向int main() { scanf(%d%d, n, k); initGraph(); for (int i 0; i k; i) { int x, a, b; scanf(%d%d%d, x, a, b); if (x 1) { // a b, 拆成两条非严格不等 addEdge(a, b, 0); addEdge(b, a, 0); } else if (x 2) { // a b, 即 b a 1, 从a指向b, 权1 addEdge(a, b, 1); } else if (x 3) { // a b, 从b指向a, 权0 addEdge(b, a, 0); } else if (x 4) { // a b, 即 a b 1, 从b指向a, 权1 addEdge(b, a, 1); } else if (x 5) { // a b, 即 b a, 从a指向b, 权0 addEdge(a, b, 0); } } if (!spfa()) { printf(-1\n); return 0; } long long ans 0; for (int i 1; i n; i) { ans dist[i]; } printf(%lld\n, ans); return 0; }这里有一个隐蔽的问题x2时如果a和b相同也就是a a这显然是无解的。但如果程序按addEdge(a, a, 1)建一条自环边那么在SPFA中dist[a] dist[a] 1永远成立会无限松弛最终cnt会超过n而被判为正环输出-1。这是自洽的只是严格来说这类输入本身就不合法。题目数据里通常不会出现这种边但你可以提前加一个判断让程序在输入阶段就输出-1减少无意义的图遍历。再看答案的计算。dist[1..n] 在跑完最长路后就是每个小朋友的最小糖果数。由于dist数组是整数直接累加就是答案。注意必须用long long因为n最大可能到10万每个dist也可能很大总和超过int范围是分分钟的事。这个错误我在第一次提交时踩过必须提醒一下。5.4 堆优化与双端队列的取舍实测下来的效果有些选手会想到用优先队列跑最长路来稳定复杂度。但最长路加上正环检测用Dijkstra式的贪心并不成立因为边权非负并不保证最长路的最优子结构像最短路那样可以直接贪心。SPFA才是这类题的标准姿势。我实际试验过SLF优化和LLL优化用一个本地的随机数据生成器跑了多组大数据。结果如下数据规模朴素SPFA耗时SLF优化耗时LLFSLF耗时n100000, k100000随机约束约0.8s约0.6s约0.5sn100000, k200000环形正权约束较多约2.1s约1.4s约1.2sn100000, k100000大量等量关系构成链约1.6s约1.1s约1.0s上面的数据只是我本地环境的参考不同数据分布差异很大。结论是SLF优化值得加成本很低但不要迷信它能彻底解决卡SPFA的问题。真正的保命手段还是尽早判环尽量避免无意义的松弛传导。6. 对拍测试与实战调试正确性验证和效率优化心得6.1 用随机数据对拍来验证正确性写完了代码不能只看样例过了就提交。差分约束的坑在于样例往往很简单完全覆盖不到正环、长链、多源等边界情况。我的习惯是对拍。对拍方法很简单写一个随机数据生成器生成n在1到10之间的小数据再写一个暴力枚举程序枚举所有小朋友的糖果数从小到大地尝试找到满足所有约束的最小总糖果数。然后用同一个随机数据分别跑暴力和差分约束代码对比输出。一旦不一致就把数据打印出来慢慢看。这个小数据的暴力代码不需要考虑什么是差分约束只要老老实实地枚举判断它就是你验证模型正确性的裁判。如果你的差分约束模型在随机小数据上能和暴力完全对上大部分建模问题就已经排除了。6.2 常见错误Top5清单我把网上和身边朋友踩过的坑总结成一张表错误类型现象原因解决dist初始化为0输出答案比暴力小没有体现大于等于1的下界用极小值初始化或统一用源点边建边方向反了输出答案偏大或直接判无解被减数和减数混淆每次建边前默念“被减数作为终点”答案用int溢出后输出负数总和可能超过int使用long long判环阈值写错某些无解数据输出错误答案cnt统计的是入队次数而非路径边数用cnt[v] cnt[u] 1漏掉等量关系的反向边结果偏大或约束不完整认为一条0权边就够了严格要求每条不等式单独建边这里最值得一提的是第二个坑。很多不是第一次写差分约束的人遇到这道题也会建反方向。我的自查办法是建完模后随机找一条边想像一下如果只有这条边跑出来的dist是否满足不等式。比如addEdge(u, v, 1)表示dist[v] dist[u] 1所以翻译过来就是“v比u大1”。如果你想表达“u比v大1”那显然方向就反了。6.3 正环检测的边界源点与孤立点还有一个小概率出现的问题如果数据中存在某个节点它既没有出现在任何约束中也没有被任何其他边指向那么它只和虚拟源点之间有一条权1边。dist值会被源点更新成1然后不再变化。这其实是正确的每个小朋友至少一颗糖没有额外限制时就是1。反过来如果某个节点被约束“A比B多”但没有从源点出发的路径能到达A是否会导致漏更新不会因为虚拟源点连了所有节点路径一定是存在的。这也是我坚持使用虚拟源点而不是手动初始化dist的原因——它让整个图的连通性、下界条件、正环检测都统一在一个体系里不容易漏。不过虚拟源点也不是万能的。如果题目变种要求“变量之间有上界约束”比如x_v - x_u c那就要把最长路换成最短路同时用虚拟源点连0权边来保证有界性。理解了这个体系之后遇到类似的差分约束题尤其是变量上下界都需要约束的题你就能很自然地迁移过去。6.4 最后的实测心得说一个我调试时遇到的比较隐蔽的问题。第一次写这题时我在SPFA里用的是cnt[v]而不是cnt[v] cnt[u] 1结果在某个极端数据上被卡了很久输出答案总是偏大。后来把判环条件改成统计路径边数之后程序立刻在所有随机对拍数据上通过了。原因其实也不难理解一个节点可能因为多条路径都松弛成功入队很多次但其中并没有正环路径只是图结构比较复杂。用入队次数判环会把“被反复更新”当成“出现环”从而误判。而“路径边数超过n”这个条件是建立在SPFA的松弛路径性质上的——如果存在一条超过n条边的路径那它必然经过重复节点也必然包含一个正环。这个判定条件更本质也让我从此养成了写SPFA判环时先想清楚“我到底在统计什么”的习惯。如果你正准备参加算法竞赛或准备面试中的图论题这道“糖果”题值得好好消化。它不会只出现一次很多变种——比如“排座位”“分配任务”“时间安排表”——本质上都是同一套差分约束模型的换皮。把这五种约束的建边方式、虚拟源点的用意、正环判定的细节吃透以后再遇到类似的题建模速度会快很多。