差分约束问题浅谈

—— by dsfz l1ll5

图论 最短路 差分约束

写在前面的话

图论我不太会，这个东西我也不太会，但是既然都决定啦，就让我来讲当总书记，所以写了篇这个东西...
晚上赶工的成品...有错误欢迎随时骂我。

有什么用

可以用来解一类不等式组，其中的每个不等式为如下形式：

即两个未知量的差不等于某常数。
显然的，可以发现此处的不等号不等式的形式并不影响，可以通过两遍均乘 $-1$ 和 $k\pm 1$ 来完成转化。

然这样的不等式组要么无解，要么有无数种解，因为当我们求出一组特解 $X$ 后，将每个未知量置为 $x_i+\Delta$ 后显然也是一组可行解。

数和图的转化

考虑常见的单源最短路算法实现，均考虑到如下的三角形不等式。

若存在边 $(u,v)$ 则一定有：

于是在算法迭代的过程中按此规则多次迭代，即可得到单源最短路的解。
发现这个式子和上式很像，若将 $dis_x$ 视为一个未知量，则两个问题的形式是完全相同的。

所以对于我们的不等式组，按照如下规则建图：

对于不等式 $X_i-X_j \leq k$ ，建边 $j \rightarrow i$ ，权值为 $k$

可以发现，当我们求出单源最短路后，这个最短路的解一定满足每个三角形不等式，即满足每条边——原不等式组中每条不等式的限制。
那么让我们愉快的求最短路吧...? 有个问题是发现我们没有原点，即没有一个已知的源点 $S$ 满足 $dis_S=0$ 来让我们启动这个算法。

既然没有困难，就让我们创造困难

一个常见的套路是直接建立虚拟源点 $S=0$ ，对于 $S$ ，设立如下不等式组：

我们钦定 $X_0=0$ ，可以发现 $X_0$ 的取值对答案没有影响。因为如果存在一组解，那么存在无数组解，一定存在某组解满足我们钦定的 $X_0$ 。如果不存在解，显然多了几条限制更不会有解了...

所以我们可以对这个模型大力最短路，求出的就是一组可行解了。

更进一步，这组可行解是在钦定 $X_0=0$ 情况下的最大解。
如果你理解了以上的内容，可以发现这里的最大解对于每个解和这些解的和而言都取到了最大。并且若存在解必定存在一组这样的最大解。

为什么呢？
考虑最短路算法的迭代流程，首先置 $X_i=inf$ ，按照三角形不等式迭代直至得到解 $f_1,f_2...,f_n$ 。
令最大解为 $g_1,g_2,...,g_n$ ，我们置 $X_i=g_i$ ，显然直接满足所有三角形不等式，得到解 $g_1,g_2,...,g_n$

最短路问题有解则一定有唯一解，否则迭代未稳定，则一定有 $f_i = g_i$

这个解的实际意义为，每个未知量均为非正整数时的最大解。
相对的，如果求每个未知量均为非负整数时的最小解，转换最短路模型为最长路模型即可，细节可以自己思考下。

关于无解情况的判定，图中存在负环则无解， dijkstra 算法无法解决这个问题，我们通常采用 SPFA 算法在执行最短路的同时判断负环。

负环怎么判呢？ 一个节点在 SPFA 的过程中入队超过 $n$ 次则存在负环，显然这个判断复杂度是 $O(nm)$ 的...
另一个判断方法是把 SPFA 写成 dfs 版的，这样判断是否重复入栈即可，相对不好卡了一点所以很多时候跑的飞快。

练习

例 1

幼儿♂园里有 $n$ 个 $boys$，$ltx$ 老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。但是小朋友们没有许容之心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候， $ltx$ 需要满足小朋友们的 $k$ 个要求。幼儿园的糖果总是有限的，$ltx$ 想知道至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。

输入的第一行是两个整数 $n$，$k$。
接下来K行，表示这些点需要满足的关系，每行3个数字，$X$，$A$，$B$。
如果 $X=1$， 表示第 $A$ 个小朋友分到的糖果必须和第 $B$ 个小朋友分到的糖果一样多；
如果 $X=2$， 表示第 $A$ 个小朋友分到的糖果必须少于第 $B$ 个小朋友分到的糖果；
如果 $X=3$， 表示第 $A$ 个小朋友分到的糖果必须不少于第 $B$ 个小朋友分到的糖果；
如果 $X=4$， 表示第 $A$ 个小朋友分到的糖果必须多于第 $B$ 个小朋友分到的糖果；
如果 $X=5$， 表示第 $A$ 个小朋友分到的糖果必须不多于第 $B$ 个小朋友分到的糖果；

题目经过魔改，练习建图用。

写出不等式大力跑即可。

BZOJ 2330 [SCOI2011]糖果

例 2

给出一组差分约束系统判断是否存在可行解。

BZOJ 3436 小 K 的农场

例 3

BZOJ 1731 [Usaco2005 dec]Layout 排队布局

没想到什么有意思的题... 就丢出来大家自己去做一做吧...

THX