题目描述：
幼儿园里有 N 个小朋友，老师现在想要给这些小朋友们分配糖果，要求每个小朋友都要分到糖果。
但是小朋友们也有嫉妒心，总是会提出一些要求，比如小明不希望小红分到的糖果比他的多，于是在分配糖果的时候， 老师需要满足小朋友们的 K 个要求。
幼儿园的糖果总是有限的，老师想知道他至少需要准备多少个糖果，才能使得每个小朋友都能够分到糖果，并且满足小朋友们所有的要求。
输入格式
输入的第一行是两个整数 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 个小朋友分到的糖果。小朋友编号从 1 到 N。
输出格式
输出一行，表示老师至少需要准备的糖果数，如果不能满足小朋友们的所有要求，就输出 −1。
数据范围
1≤N<10^5, 1≤K≤10^5, 1≤X≤5, 1≤A,B≤N
输入样例：
5 7 1 1 2 2 3 2 4 4 1 3 4 5 5 4 5 2 3 5 4 5 1输出样例：
11分析：
本题考查差分约束。如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束系统(system of difference constraints)。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。简而言之，差分约束就是用来求解一种特殊的不等式组，这种不等式组里面不等式的格式都是类似于Xa <= Xb + c这种形式，差分约束问题可以用求单源最短路的算法来求解，一般使用spfa算法求解。
1.差分约束问题与最短路问题的联系
在求解最短路的算法中，核心的语句就是松弛操作，即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]看作Xa，所有与之相邻的点看作Xb，则求完最短路径后的{Xa,Xb}的值一定满足形如Xa <= Xb + c的不等式组的要求，也就是说，可以用spfa求最短路的过程来求解差分约束问题。
2.不等式组解的最小值与最大值
在求最短路的过程中，如果起点s的距离设为0，设从起点到某点t的路径上依次经过x1，x2，x3三个点，对应的边权依次是c1，c2，c3。则有x1 <= s + c1，x2 <= x1 + c2，x3 <= x2 + c3，可以推出x3 <= x2 + c3 <= x1 + c2 + c3 <= s + c1 + c2 + c3，s在这里是定值，可以看出x3的值不会超过s + c1 + c2 + c3，也就是可以找到x3的最大值，但是不一定能够知道x3的最小值，其他变量x1，x2也均有个上限，所以求最短路得到的解实际上是不等式组的最大解。当然，在松弛过程中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的路径上依次经过x1，x2，x3三个点，对应的边权依次是c1，c2，c3。则有x1 >= s + c1，x2 >= x1 + c2，x3 >= x2 + c3，可以推出x3 >= x2 + c3 >= x1 + c2 + c3 >= s + c1 + c2 + c3，s在这里是定值，可以看出x3的值不会小于s + c1 + c2 + c3，这样就求出了x3的最小值了，也就是说最长路可以求出不等式组的最小解。注意，最长路算法求解的是形如xa >= xb + c这种形式的不等式。
3.无约束的变量与无解情况
假设图中有一点是孤立的，与其他点没有关联边，则对应差分约束问题中的变量就是不受约束的，可以取任意值。再来考察无解的情况，如果求最短路时存在负环，假设负环上的点有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的矛盾结论了。
4.差分约束问题的建图
找到了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使用队列会超时，所以要用栈替换队列。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 100005,M = 300005; int idx,h[N],e[M],w[M],ne[M]; bool st[N]; int n,k,d[N],q[N],cnt[N]; void add(int a,int b,int c){ e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx++; } bool spfa(){ memset(d,-0x3f,sizeof d); memset(st,false,sizeof st); memset(cnt,0,sizeof cnt); int hh = 0; q[hh++] = 0; d[0] = 0; st[0] = true; while(hh){ int u = q[--hh]; st[u] = false; for(int i = h[u];~i;i = ne[i]){ int j = e[i]; if(d[j] < d[u] + w[i]){ d[j] = d[u] + w[i]; cnt[j] = cnt[u] + 1; if(cnt[j] >= n + 1) return false; if(!st[j]){ q[hh++] = j; st[j] = true; } } } } return true; } int main(){ scanf("%d%d",&n,&k); int a,b,x; memset(h,-1,sizeof h); for(int i = 0;i < k;i++){ scanf("%d%d%d",&x,&a,&b); if(x == 1) add(a,b,0),add(b,a,0); else if(x == 2) add(a,b,1); else if(x == 3) add(b,a,0); else if(x == 4) add(b,a,1); else add(a,b,0); } for(int i = 1;i <= n;i++) add(0,i,1); if(!spfa()) puts("-1"); else{ long long res = 0; for(int i = 1;i <= n;i++){ res += d[i]; } printf("%lld\n",res); } return 0; }
