差分约束系统

· · 个人记录

前置知识：负环

差分约束系统是一种特殊的不等式组，包含 n 个变量，m 个约束条件。约束条件形如 x_i-x_j\leq c_k。求解差分约束系统可以用 SPFA，时间复杂度 O(nm)，部分题目也可用 Floyd。

将 x_i-x_j\leq c_k 变形为 x_i\leq x_j+c_k，与最短路的松弛操作 dis_x=\min(dis_x,dis_y+len) 相似，因此从 j 向 i 连长度为 c_k 的有向边，即可保证满足约束条件。

若求的是最长路，则变形为 x_j\geq x_i-c_k，从 i 向 j 连长度为 -c_k 的边即可。

判无解的方式：若求的是最短路，判负环，否则判正环。

部分差分约束系统的题目有一些隐含条件，不要忘记连上对应的边。有时还要建一个虚拟源点 0，向其他点连长度为 0 的边，以保证图连通。

例题：P5751 [NOI1999]01串

设 x_i 表示 S 的前 i 位中 1 的个数，初始值 x_0=0。以 x_0,x_1...x_n 作为差分约束系统的变量。对于两种限制分别转化为不等式连边即可。

注意隐含条件：0\leq x_i-x_{i-1}\leq 1，对于相邻两个数也要连边。

最后以 0 为起点跑 SPFA 判负环即可。

如何保证 1 的个数最大？

差分约束系统有一个性质，求出的最短路一定是满足条件的最大值，最长路一定是最小值。

感性理解：求最短路时，约束条件是 x_i\leq x_j+c_k，松弛时 dis_i=dis_j+c_k，由小于等于变成等于，因此 dis_i 是满足约束条件的最大值。

习题（按难度排序）：

P2474 [SCOI2008]天平

P3530 [POI2012]FES-Festival

P5590 赛车游戏

P7515 [省选联考 2021 A 卷] 矩阵游戏 题解

参考资料：差分约束 - OI Wiki