恩，本篇文章再写一点深入的思考。忽然发现我的博客开始走找各种被人忽略的细节的路线了。今天要为大家带来的是差分约束的两个题，并且会为大家说明一下自己做这题时候的思考和网上流传的一些错误，不想让网上抄来抄去的东西误导了大家的思路。OJ数据弱，这个是真的，题目那么多，不能保证每个题测试数据的质量，所以很多错误的程序也能过，导致了大家可能把错误的思路也认为是正确的了。恩，下面开始正文。
POJ 3169
题意：n头牛站在x轴上，并且x[1]<=x[2]<=...<=x[n]，然后给定了一些喜欢的关系和讨厌的关系，喜欢的关系是（a，b，c）代表牛a和牛b的距离不才能超过c，讨厌的关系也是（a，b，c）代表牛a和牛b的距离至少是c，然后求牛1和牛n的最大距离是多少。如果没有合法的站位，输出-1；如果牛1和牛n可以无穷远，输出-2；否则输出牛1和牛n的最大距离。
这个题看上去很水的，差分约束的题，按照“最长路求最小值，最短路求最大值”的理论建图就行了。需要注意的一个细节就是，如果同时满足没有合法的站位和牛n牛1可以相距无穷远，那么按照题意应该是输出-1的，但是貌似标程是认为-2的优先级高于-1了，而且OJ数据比较弱，没有这种情况的出现，所以不管你输出-1还是-2都能AC。这种情况下，会导致大家思考的时候忽略了一个细节，就是spfa求负环的时候（如果最开始只是原点入队列的话），那么只能判一个原点可达的负环，原点不可达的负环是判不出来的。那怎么办呢？我做法是两次spfa，一次是判负环（所有点入队列，距离都为0），一次是求最短路（原点入队列，距离为0，其他点距离INF）。后来一直再想一次同时求出最短路和判负环的构图方法，n久没想出来。不过自己想了下，有一种方法，虽然是做两次spfa，但是程序执行时间上和一次spfa是一样的，做法是先做spfa，做完之后把所有标号为INF的点加入到队列中去，然后在上一次做完spfa的基础上再spfa判负环。做完了之后，总感觉不爽，就没有一次构图能解决问题的办法么？
后来和别人讨论了一下，发现了一种办法。这种办法要利用到最短路径上限的值。假设如果没有负环，最长路径值设为max，那么如果开始的时候将原点距离定为0，其他点距离定义为2*max，并且开始时把所有点入队列（和建立一个虚拟原点是一样的）如果有负环的话会返回负环，如果没有的话，判断d[n]和max的关系，如果d[n]>max，那么认为不可达，否则可达。这个方法很巧妙，需要细细思考一下。
这题还有值得思考的一个地方就是，为什么是最短路求最大值，最长路求最小值。拿最短路求最大值说，如果建立的是这样的边v<=u+w，那么其实v的值可以更小的，比如v=5满足条件，那么v=4也满足条件，但是最短路求的时候用的是等号，所以求的就是满足条件的所有值中最大的那个。另外最大值和最小值一定要看你定义的原点是谁，如果定义原点是1，那么求n的最大值；如果定义原点为n，那么求1的最小值。
POJ 1275
题意：24个小时每个小时都要有人值班，告诉你每个小时最少需要值班的人数，然后告诉你每个可以用的员工工作的起始时间，每个员工工作的时间都是8个小时，问至少需要多少个员工能完成工作。
这题也是差分约束，差分方程很好写
(1) s[i]-s[i-8]>=R[i] (8<=i<=24)
(2) s[i]-s[16+i]>=R[i]-s[24] (1<=i<=7)
(3) s[i]-s[i-1]>=0 (1<=i<=24)
(4) s[i-1]-s[i]>=-T[i] (1<=i<=24)
关键是第二个方程，有三个未知数，这时可以枚举s[24]=sum，然后建立新的方程组
(1) s[i]-s[i-8]>=R[i] (8<=i<=24)
(2') s[i]-s[16+i]>=R[i]-sum (1<=i<=7)
(3) s[i]-s[i-1]>=0 (1<=i<=24)
(4) s[i-1]-s[i]>=-T[i] (1<=i<=24)
(5) s[24]-s[0]>=sum
相信做这个题的人看了网上的解释都知道要加（5）的原因，说是如果求出的s[24]小于sum，那么原来的方程（2）就不一定满足了，所以要加（5）这个方程来限制；并且如果求出的值s[24]>sum的话，那么把s[24]减小为sum一定是一个原方程的解，并且，结尾不需要判断s[24]==sum。这段话在discuss和网上的好多博客中都有说明。好了，重头戏来了，不需要判s[24]==sum么？
需要！！！OJ数据弱，所以不判也能过。问大家一句，为什么只看方程（2），如果你求出的s[24]大于sum，那方程（1）满足么？如果求出s[24]=sum+10，那么把s[24]减小为sum的话（1）方程就不一定满足了。举个更简单的例子来说
有三个差分个方程
x>=17
y>=x
y>=16
如果你枚举了x=14，然后又加了一个方程x>=14，那么这种情况会得到x>=17，y>=16。是不矛盾的，图中没有负环，但是x=14是方程的合法解吗？显然不是，因为还有x>=17这个条件没有满足。如果还是不理解，那么就自己造一组数据，只有23~24点需要17个人工作，并且一共5个人可用，每个人起始工作时间都是23点，看看如果不判s[24]==sum会输出什么吧。
PS：我最开始做这个题枚举sum的时候，建立了一个环，s[24]>=sum和s[24]<=sum。
差分约束关键只是在于建图，剩下的就是求最短路或者最长路，spfa比较合适，反正不能用dijkstra就是了，因为一般差分约束的题中都有负权边。这里不贴代码了。
Comments