AcWing 1169 分糖果

分析：

本题考查差分约束。如果一个系统由\(n\)个变量和\(m\)个约束条件组成，其中每个约束条件形如
\(x_j-x_i<=b_k(i,j∈[1,n],k∈[1,m])\),则称其为差分约束系统(\(system\) \(of\) \(difference\) \(constraints\))。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。简而言之，差分约束就是用来求解一种特殊的不等式组，这种不等式组里面不等式的格式都是类似于\(X_a <= X_b + c\)这种形式，差分约束问题 可以 用求单源最短路的算法来求解，一般使用\(spfa\)算法求解。

一、差分约束问题与最短路问题的联系

在求解最短路的算法中，核心的语句就是松弛操作，即\(d[v] > d[u] + w\)，就可以更新\(d[v]\)为\(d[u] + w\)了。在松弛某点\(v\)的距离的时候，会考察所有可以到达\(v\)的相邻点，每次从\(v\)的相邻点尝试去松弛\(v\)之后，都会有\(d[v] <= d[u] + w\)，所以最终最短路径上\(d[v] = min(d[i] + w[i])\)。如果将\(d[v]看作X_a\)，所有与之相邻的点看作\(X_b\)，则求完最短路径后的{\(X_a\),\(X_b\)}的值一定满足形如\(X_a <= X_b + c\)的不等式组的要求，也就是说，可以用\(spfa\)求最短路的过程来求解差分约束问题。

二、不等式组解的最小值与最大值

在求最短路的过程中，如果起点\(s\)的距离设为\(0\)，设从起点到某点\(t\)的路径上依次经过\(x_1，x_2，x_3\)三个点，对应的边权依次是\(c_1，c_2，c_3\)。则有\(x_1 <= s + c_1\)，\(x_2 <= x_1 + c_2\)，\(x_3 <= x_2 + c_3\)，可以推出\(x_3 <= x_2 + c_3 <= x_1 + c_2 + c_3 <= s + c_1 + c_2 + c_3\)，\(s\)在这里是定值，可以看出\(x_3\)的值不会超过\(s + c_1 + c_2 + c_3\)，也就是可以找到\(x_3\)的最大值，但是不一定能够知道\(x_3\)的最小值，其他变量\(x_1\)，\(x_2\)也均有个上限，所以求最短路得到的解实际上是不等式组的最大解。当然，在松弛过程中\(d[v] = min(d[i] + w[i])\)，也就是为了满足所有的约束条件，\(d[v]\)实际上是取所有松弛结果的最小值的。

再来考察求最长路的过程，将求最短路的松弛条件倒过来就可以求最长路了，即\(d[v] < d[u] + w\)时，就更新\(d[v]\)为\(d[u] + w\)，最后\(d[v] = max(d[i] + w[i])\)，也就是求完最长路后\(d[v] >= d[u] + w\)。同样的如果起点\(s\)的距离设为\(0\)，设从起点到某点\(t\)的路径上依次经过\(x_1，x_2，x_3\)三个点，对应的边权依次是\(c_1，c_2，c_3\)。则有\(x_1 >= s + c_1，x_2 >= x_1 + c_2，x_3 >= x_2 + c_3\)，可以推出\(x_3 >= x_2 + c_3 >= x_1 + c_2 + c_3 >= s + c_1 + c_2 + c_3\)，\(s\)在这里是定值，可以看出\(x_3\)的值不会小于\(s + c_1 + c_2 + c_3\)，这样就求出了\(x_3\)的最小值了，也就是说求最长路可以求出不等式组的最小解。注意，最长路算法求解的是形如\(x_a >= x_b + c\)这种形式的不等式。

三、无约束的变量与无解情况

假设图中有一点是孤立的，与其他点没有关联边，则对应差分约束问题中的变量就是不受约束的，可以取任意值。再来考察无解的情况，如果求最短路时存在负环，假设负环上的点有x1，x2，x3，则有x2 <= x1 + c1，x3 <= x2 + c2，x1 <= x3 + c3，可以推出x1 <= x3 + c3 <= x2 + c2 + c3 <= x1 + c1 + c2 + c3，又c1 + c2 + c3 < 0（存在负环），所以x1 <= x1 + c1 + c2 + c3 < x1得出了x1 < x1的矛盾结论了，所以spfa算法如果求出了负环则说明差分约束问题无解。

求最长路时如果存在正环，设正环上的点有x1，x2，x3，则有x2 >= x1 + c1，x3 >= x2 + c2，x1 >= x3 + c3，可以推出x1 >= x3 + c3 >= x2 + c2 + c3 >= x1 + c1 + c2 + c3，又c1 + c2 + c3 > 0（存在正环），所以x1 >= x1 + c1 + c2 + c3 > x1得出了x1 > x1的矛盾结论了。

四、差分约束问题的建图

找到了spfa算法可以求解差分约束问题，下面需要做的就是将不等式组转化为图。建图的过程深刻的反映了求最短路最长路与差分约束问题的关联。比如x1 <= x2 + 1，是建一条x2到x1长度为1的边，还是建一条x1到x2长度为-1的边呢？在最短路问题中，我们需要x1 <= x2 + c这种形式的不等式，遇见x1 >= x2 + 1形式的不等式就 转化为了x2 <= x1 - 1，从而建立了x1到x2长度为-1的边。而在最长路问题中，遇见x1 >= x2 + 1可以建一条x2到x1长度为1的边，遇见x1 <= x2 + 1这种形式的不等式可以转化为x2 >= x1 - 1，建立起了x1到x2长度为-1的边。从而得出了一个重要结论：同一个不等式在最长路和最短路问题中建图的方向是相反的，建立的边权互为相反数，比如x1 <= x2 + 1，最短路问题是建一条x2到x1长度为1的边，而在最长路问题中则是建一条x1到x2长度为-1的边（x2 >= x1 - 1）。

其他类型的不等式：对于x1 < x2 + c形式的不等式，可以转化为x1 <= x2 + c - 1形式；对于x1 = x2形式的不等式，可以转化为x1 <= x2和x2 <= x1两个不等式。

由于建的图不一定连通，所以为了保证从起点出发一定能到达所有点，一般会建一个超级源点，从这个超级源点向各个点引一条长度为0的边，即在不等式组中加上了x0 <= x1,x0 <= x2,...,x0 <=xn这么多不等式。

下面回归本题，由于每个小朋友都需要分到糖，所以某个变量都不能小于1，所以建图时可以由x0向各点引一条长度为1的边，因为要求x1 >= 1等价于x1 >= x0 + 1,x0 = 0。本题是求差分约束的最小解，所以需要求最长路。spfa算法求最长路时需要将距离数组初始化为负无穷，当存在正环时存在某个点会一直被更新，所以更新超过一定次数后就说明无解。本题的spfa使用队列会超时，所以要用栈替换队列。