Sunday, January 10, 2016

夜深人静写算法(四) - 差分约束


http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html
       1、一类不等式组的解
      给定n个变量和m个不等式,每个不等式形如 x[i] - x[j] <= a[k] (0 <= i, j < n, 0 <= k < m, a[k]已知),求 x[n-1] - x[0] 的最大值。例如当n = 4,m = 5,不等式组如图一-1-1所示的情况,求x3 - x0的最大值。
图一-1-1
      观察x3 - x0的性质,我们如果可以通过不等式的两两加和得到c个形如 x3 - x0 <= Ti 的不等式,那么 min{ Ti | 0 <= i < c } 就是我们要求的x3 - x0的最大值。于是开始人肉,费尽千辛万苦,终于整理出以下三个不等式:
      1.      (3)                       x3 - x0 <= 8
      2.      (2) + (5)              x3 - x0 <= 9
      3.      (1) + (4) + (5)     x3 - x0 <= 7
      这里的T等于{8, 9, 7},所以min{ T } = 7,答案就是7。的确是7吗?我们再仔细看看,发现的确没有其它情况了。那么问题就是这种方法即使做出来了还是带有问号的,不能确定正确与否,如何系统地解决这类问题呢?
      让我们来看另一个问题,这个问题描述相对简单,给定四个小岛以及小岛之间的有向距离,问从第0个岛到第3个岛的最短距离。如图一-1-2所示,箭头指向的线段代表两个小岛之间的有向边,蓝色数字代表距离权值。


图一-1-2
      这个问题就是经典的最短路问题。由于这个图比较简单,我们可以枚举所有的路线,发现总共三条路线,如下:
      1.       0 -> 3                       长度为8
      2.       0 -> 2 -> 3               长度为7+2 = 9
      3.       0 -> 1 -> 2 -> 3       长度为2 + 3 + 2 = 7
      最短路为三条线路中的长度的最小值即7,所以最短路的长度就是7。这和上面的不等式有什么关系呢?还是先来看看最短路求解的原理,看懂原理自然就能想到两者的联系了。


二、最短路
      1、Dijkstra
      对于一个有向图或无向图,所有边权为正(边用邻接矩阵的形式给出),给定a和b,
求a到b的最短路,保证a一定能够到达b。这条最短路是否一定存在呢?答案是肯定的。相反,最长路就不一定了,由于边权为正,如果遇到有环的时候,可以一直在这个环上走,因为要找最长的,这样就使得路径越变越长,永无止境,所以对于正权图,在可达的情况下最短路一定存在,最长路则不一定存在。这里先讨论正权图的最短路问题。
      最短路满足最优子结构性质,所以是一个动态规划问题。最短路的最优子结构可以描述为:
      D(s, t) = {Vs ... Vi ... Vj ... Vt}表示s到t的最短路,其中i和j是这条路径上的两个中间结点,那么D(i, j)必定是i到j的最短路,这个性质是显然的,可以用反证法证明。
      基于上面的最优子结构性质,如果存在这样一条最短路D(s, t) = {Vs ... Vi Vt},其中i和t是最短路上相邻的点,那么D(s, i) = {Vs ... Vi} 必定是s到i的最短路。Dijkstra算法就是基于这样一个性质,通过最短路径长度递增,逐渐生成最短路。
      Dijkstra算法是最经典的最短路算法,用于计算正权图的单源最短路(Single Source Shortest Path,源点给定,通过该算法可以求出起点到所有点的最短路),它是基于这样一个事实:如果源点到x点的最短路已经求出,并且保存在d[x] ( 可以将它理解为D(s, x) )上,那么可以利用x去更新 x能够直接到达的点 的最短路。即:
      d[y] = min{ d[y], d[x] + w(x, y) }           y为x能够直接到达的点,w(x, y) 则表示x->y这条有向边的边权
      具体算法描述如下:对于图G = <V, E>,源点为s,d[i]表示s到i的最短路,visit[i]表示d[i]是否已经确定(布尔值)。
      1) 初始化 所有顶点 d[i] = INF, visit[i] = false,令d[s] = 0;
      2) 从所有visit[i]为false的顶点中找到一个d[i]值最小的,令x = i; 如果找不到,算法结束;
      3) 标记visit[x] = true, 更新和x直接相邻的所有顶点y的最短路: d[y] = min{ d[y], d[x] + w(x, y) }
     (第三步中如果y和x并不是直接相邻,则令w(x, y) = INF)
      4Dijkstra + 优先队列(小顶堆)
      有了链式前向星,再来看Dijkstra算法,我们关注算法的第3)步,对和x直接相邻的点进行更新的时候,不再需要遍历所有的点,而是只更新和x直接相邻的点,这样总的更新次数就和顶点数n无关了,总更新次数就是总边数m,算法的复杂度变成了O(n^2 + m),之前的复杂度是O(n^2),但是有两个n^2的操作,而这里是一个,原因在于找d值最小的顶点的时候还是一个O(n)的轮询,总共n次查找。那么查找d值最小有什么好办法呢?
      数据结构中有一种树,它能够在O( log(n) )的时间内插入和删除数据,并且在O(1)的时间内得到当前数据的最小值,这个和我们的需求不谋而合,它就是最小二叉堆(小顶堆),具体实现不讲了,比较简单,可以自行百度。
      在C++中,可以利用STL的优先队列( priority_queue )来实现获取最小值的操作,这里直接给出利用优先队列优化的Dijkstra算法的类C++伪代码(请勿直接复制粘贴到C++编译器中编译执行),然后再进行讨论:
    void Dijkstra_Heap(s) {
                    for(i = 0; i < n; i++) {   
            d[i] = (i == s) ? 0 : INF;  // 注释1
        }
        q.push( (d[s], s) );            // 注释2
                    while!q.empty() ) {
            (dist, u) = q.top();        // 注释3
            q.pop();                    // 注释4
                              for (e = head[u]; e != INF; e = edge[e].next) {
                v = edge[e].v;
                w = edge[e].w;
                                        if(d[u] + w < d[v]) {
                    d[v] = d[u] + w;
                    path[v] = u;
                    q.push( (d[v], v) );
                }
            }
        }
    }
   注释1:初始化s到i的初始最短距离,d[s] = 0
   注释2:q即优先队列,这里略去声明是为了将代码简化,让读者能够关注算法本身而不是关注具体实现,   push是执行优先队列的插入操作,插入的数据为一个二元组(d[u], u)
   注释3:执行优先队列的获取操作,获取的二元组为当前队列中d值最小的
   注释4:执行优先队列的删除操作,删除队列顶部的元素(即注释3中d值最小的那个二元组)
      以上伪代码中的主体部分竟然没有任何注释,这是因为我要用黑色的字来描述它的重要性,而注释只是注释一些和语法相关的内容。
      主体代码只有一个循环,这个循环就是遍历了u这个结点的边链表,其中e为边编号,edge[e].w即上文提到的w(u, v),即u ->v 这条边的权值,而d[u] + w(u, v) < d[v]表示从起点s到u,再经过(u, v)这条边到达v的最短路比之前其它方式到达v的最短路还短,如图二-4-1所示,如果满足这个条件,那么就更新这条最短路,并且利用path数组来记录最短路中每个结点的前驱结点,path[v] = u,表示到达v的最短路的前驱结点为u。
图二-4-1
      补充一点,这个算法求出的是一棵最短路径树,其中s为根结点,结点之间的关系是通过path数组来建立的,path[v] = u,表明u为v的父结点(树的存储不一定要存儿子结点,也可以用存父结点的方式表示)。
      考虑这个算法的复杂度,如果用n表示点数,m表示边数,那么优先队列中最多可能存在的点数有多少?因为我们在把顶点插入队列的时候并没有判断队列中有没有这个点,而且也不能进行这样的判断,因为新插入的点一定会取代之前的点(距离更短才会执行插入),所以同一时间队列中的点有可能重复,插入操作的上限是m次,所以最多有m个点,那么一次插入和删除的操作的平摊复杂度就是O(logm),但是每次取距离最小的点,对于有多个相同点的情况,如果那个点已经出过一次队列了,下次同一个点出队列的时候它对应的距离一定比之前的大,不需要用它去更新其它点,因为一定不可能更新成功,所以真正执行更新操作的点的个数其实只有n个,所以总体下来的平均复杂度为O( (m+n)log m),而这个只是理论上界,一般问题中都是很快就能找到最短路的,所以实际复杂度会比这个小很多,相比O(n^2)的算法已经优化了很多了。
      Dijkstra算法求的是正权图的单源最短路问题,对于权值有负数的情况就不能用Dijkstra求解了,因为如果图中存在负环,Dijkstra带优先队列优化的算法就会进入一个死循环,因为可以从起点走到负环处一直将权值变小 。对于带负权的图的最短路问题就需要用到Bellman-Ford算法了。

  5Bellman-Ford
      Bellman-Ford算法可以在最短路存在的情况下求出最短路,并且在存在负权圈的情况下告诉你最短路不存在,前提是起点能够到达这个负权圈,因为即使图中有负权圈,但是起点到不了负权圈,最短路还是有可能存在的。它是基于这样一个事实:一个图的最短路如果存在,那么最短路中必定不存在圈,所以最短路的顶点数除了起点外最多只有n-1个。
      Bellman-Ford同样也是利用了最短路的最优子结构性质,用d[i]表示起点s到i的最短路,那么边数上限为 j 的最短路可以通过边数上限为 j-1 的最短路 加入一条边 得到,通过n-1次迭代,最后求得s到所有点的最短路。
      具体算法描述如下:对于图G = <V, E>,源点为s,d[i]表示s到i的最短路。
   1) 初始化 所有顶点 d[i] = INF, 令d[s] = 0,计数器 j = 0;
      2) 枚举每条边(u, v),如果d[u]不等于INF并且 d[u] + w(u, v) < d[v],则令d[v] = d[u] + w(u, v);
      3) 计数器j + +,当j = n - 1时算法结束,否则继续重复2)的步骤; 
      第2)步的一次更新称为边的“松弛”操作。
      以上算法并没有考虑到负权圈的问题,如果存在负圈权,那么第2)步操作的更新会永无止境,所以判定负权圈的算法也就出来了,只需要在第n次继续进行第2)步的松弛操作,如果有至少一条边能够被更新,那么必定存在负权圈。
      这个算法的时间复杂度为O(nm),n为点数,m为边数。
      这里有一个小优化,我们可以注意到第2)步操作,每次迭代第2)步操作都是做同一件事情,也就是说如果第k(k <= n-1)次迭代的时候没有任何的最短路发生更新,即所有的d[i]值都未发生变化,那么第k+1次必定也不会发生变化了,也就是说这个算法提前结束了。所以可以在第2)操作开始的时候记录一个标志,标志初始为false,如果有一条边发生了松弛,那么标志置为true,所有边枚举完毕如果标志还是false则提前结束算法。
      这个优化在一般情况下很有效,因为往往最短路在前几次迭代就已经找到最优解了,但是也不排除上文提到的负权圈的情况,会一直更新,使得整个算法的时间复杂度达到上限O(nm),那么如何改善这个算法的效率呢?接下来介绍改进版的Bellman-Ford 一一 SPFA。
     6SPFA
      SPFA( Shortest Path Faster Algorithm )是基于Bellman-Ford的思想,采用先进先出(FIFO)队列进行优化的一个计算单源最短路的快速算法。
      类似Bellman-Ford的做法,我们用数组d记录每个结点的最短路径估计值,并用链式前向星来存储图G。利用一个先进先出的队列用来保存待松弛的结点,每次取出队首结点u,并且枚举从u出发的所有边(u, v),如果d[u] + w(u, v) < d[v],则更新d[v] = d[u] + w(u, v),然后判断v点在不在队列中,如果不在就将v点放入队尾。这样不断从队列中取出结点来进行松弛操作,直至队列空为止。 
      只要最短路径存在,SPFA算法必定能求出最小值。因为每次将点放入队尾,都是经过松弛操作达到的。即每次入队的点v对应的最短路径估计值d[v]都在变小。所以算法的执行会使d越来越小。由于我们假定最短路一定存在,即图中没有负权圈,所以每个结点都有最短路径值。因此,算法不会无限执行下去,随着d值的逐渐变小,直到到达最短路径值时,算法结束,这时的最短路径估计值就是对应结点的最短路径值。
      那么最短路径不存在呢?如果存在负权圈,并且起点可以通过一些顶点到达负权圈,那么利用SPFA算法会进入一个死循环,因为d值会越来越小,并且没有下限,使得最短路不存在。那么我们假设不存在负权圈,则任何最短路上的点必定小于等于n个(没有圈),换言之,用一个数组c[i]来记录i这个点入队的次数,所有的c[i]必定都小于等于n,所以一旦有一个c[i] > n,则表明这个图中存在负权圈。
       接下来给出SPFA更加直观的理解,假设图中所有边的边权都为1,那么SPFA其实就是一个BFS(Breadth First Search,广度优先搜索),对于BFS的介绍可以参阅搜索入门。BFS首先到达的顶点所经历的路径一定是最短路(也就是经过的最少顶点数),所以此时利用数组记录节点访问可以使每个顶点只进队一次,但在至少有一条边的边权不为1的带权图中,最先到达的顶点的路径不一定是最短路,这就是为什么要用d数组来记录当前最短路估计值的原因了。
       最后给出SPFA的类C++伪代码(请勿直接复制粘贴到C++编译器中编译执行):

    bool spfa(s) {
                    for(i = 0; i < n; i++) {
            d[i] = (i == s) ? 0 : INF;
            inq[i] = (i == s);                  // 注释1
            visitCount[i] = 0;
        }
        q.push( (d[s], s) );
                    while!q.empty() ) { 
            (dist, u) = q.front();              // 注释2
            q.pop();
            inq[u] = false;
                              if( visitCount[u]++ > n ) {         // 注释3
                                           return true;
            }
                              for (e = head[u]; e != INF; e = edge[e].next) {
                v = edge[e].v;
                w = edge[e].w;
                                        if(d[u] + w < d[v]) {           // 注释4
                    d[v] = d[u] + w;
                                                  if ( !inq[v] ) {
                        inq[v] = true;
                        q.push( (d[v], v) );
                    }
                }
            }
        }
                    return false;
    }

   注释1:inq[i]表示结点i是否在队列中,初始时只有s在队列中;
   注释2:q.front()为FIFO队列的队列首元素;
   注释3:判断是否存在负权圈,如果存在,函数返回true;
   注释4:和Dijkstra优先队列优化的算法很相似的松弛操作;
      以上伪代码实现的SPFA算法的最坏时间复杂度为O(nm),其中n为点数,m为边数,但是一般不会达到这个上界,一般的期望时间复杂度为O(km), k为常数,m为边数(这个时间复杂度只是估计值,具体和图的结构有很大关系,而且很难证明,不过可以肯定的是至少比传统的Bellman-Ford高效很多,所以一般采用SPFA来求解带负权圈的最短路问题

三、差分约束
      1、数形结合
      介绍完最短路,回到之前提到的那个不等式组的问题上来,我们将它更加系统化。
      如若一个系统由n个变量和m个不等式组成,并且这m个不等式对应的系数矩阵中每一行有且仅有一个1和-1,其它的都为0,这样的系统称为差分约束( difference constraints )系统。引例中的不等式组可以表示成如图三-1-1的系数矩阵。
图三-1-1
      然后继续回到单个不等式上来,观察 x[i] - x[j] <= a[k], 将这个不等式稍稍变形,将x[j]移到不等式右边,则有x[i] <= x[j] + a[k],然后我们令a[k] = w(j, i),再将不等式中的i和j变量替换掉,i = v, j = u,将x数组的名字改成d(以上都是等价变换,不会改变原有不等式的性质),则原先的不等式变成了以下形式:d[u] + w(u, v) >= d[v]。
      这时候联想到SPFA中的一个松弛操作:
    if(d[u] + w(u, v) < d[v]) {
        d[v] = d[u] + w(u, v);
    }
      对比上面的不等式,两个不等式的不等号正好相反,但是再仔细一想,其实它们的逻辑是一致的,因为SPFA的松弛操作是在满足小于的情况下进行松弛,力求达到d[u] + w(u, v) >= d[v],而我们之前令a[k] = w(j, i),所以我们可以将每个不等式转化成图上的有向边:
      对于每个不等式 x[i] - x[j] <= a[k],对结点 j 和 i 建立一条 j -> i的有向边,边权为a[k],求x[n-1] - x[0] 的最大值就是求 0 到n-1的最短路。
图三-1-2
      图三-1-2 展示了 图三-1-1的不等式组转化后的图。

      2、三角不等式
      如果还没有完全理解,我们可以先来看一个简单的情况,如下三个不等式:
B - A <= c      (1)
C - B <= a      (2)
C - A <= b      (3)
      我们想要知道C - A的最大值,通过(1) + (2),可以得到 C - A <= a + c,所以这个问题其实就是求min{b, a+c}。将上面的三个不等式按照 三-1 数形结合 中提到的方式建图,如图三-2-1所示。
图三-2-1
      我们发现min{b, a+c}正好对应了A到C的最短路,而这三个不等式就是著名的三角不等式。将三个不等式推广到m个,变量推广到n个,就变成了n个点m条边的最短路问题了。

      3、解的存在性
      上文提到最短路的时候,会出现负权圈或者根本就不可达的情况,所以在不等式组转化的图上也有可能出现上述情况,先来看负权圈的情况,如图三-3-1,下图为5个变量5个不等式转化后的图,需要求得是X[t] - X[s]的最大值,可以转化成求s到t的最短路,但是路径中出现负权圈,则表示最短路无限小,即不存在最短路,那么在不等式上的表现即X[t] - X[s] <= T中的T无限小,得出的结论就是 X[t] - X[s]的最大值 不存在。
图三-3-1
      再来看另一种情况,即从起点s无法到达t的情况,如图三-3-2,表明X[t]和X[s]之间并没有约束关系,这种情况下X[t] - X[s]的最大值是无限大,这就表明了X[t]和X[s]的取值有无限多种
图三-3-2
      在实际问题中这两种情况会让你给出不同的输出。综上所述,差分约束系统的解有三种情况:1、有解;2、无解;3、无限多解

      4、最大值 => 最小值
      然后,我们将问题进行一个简单的转化,将原先的"<="变成">=",转化后的不等式如下:
B - A >= c      (1)
C - B >= a      (2)
C - A >= b      (3)
      然后求C - A的最小值,类比之前的方法,需要求的其实是max{b, c+a},于是对应的是图三-2-1从A到C的最长路。同样可以推广到n个变量m个不等式的情况。
      
      5、不等式标准化
      如果给出的不等式有"<="也有">=",又该如何解决呢?很明显,首先需要关注最后的问题是什么,如果需要求的是两个变量差的最大值,那么需要将所有不等式转变成"<="的形式,建图后求最短路;相反,如果需要求的是两个变量差的最小值,那么需要将所有不等式转化成">=",建图后求最长路。
      如果有形如:A - B = c 这样的等式呢?我们可以将它转化成以下两个不等式:
A - B >= c      (1)
A - B <= c      (2)
       再通过上面的方法将其中一种不等号反向,建图即可。
       最后,如果这些变量都是整数域上的,那么遇到A - B < c这样的不带等号的不等式,我们需要将它转化成"<="或者">="的形式,即 A - B <= c - 1。
四、差分约束的经典应用
      1、线性约束
        线性约束一般是在一维空间中给出一些变量(一般定义位置),然后告诉你某两个变量的约束关系,求两个变量a和b的差值的最大值或最小值。
     【例题1】N个人编号为1-N,并且按照编号顺序排成一条直线,任何两个人的位置不重合,然后给定一些约束条件。
       X(X <= 100000)组约束Ax Bx Cx(1 <= Ax < Bx <= N),表示Ax和Bx的距离不能大于Cx。
       Y(X <= 100000)组约束Ay By Cy(1 <= Ay < By <= N),表示Ay和By的距离不能小于Cy。
       如果这样的排列存在,输出1-N这两个人的最长可能距离,如果不存在,输出-1,如果无限长输出-2。
      像这类问题,N个人的位置在一条直线上呈线性排列,某两个人的位置满足某些约束条件,最后要求第一个人和最后一个人的最长可能距离,这种是最直白的差分约束问题,因为可以用距离作为变量列出不等式组,然后再转化成图求最短路。
      令第x个人的位置为d[x](不妨设d[x]为x的递增函数,即随着x的增大,d[x]的位置朝着x正方向延伸)。
      那么我们可以列出一些约束条件如下:
      1、对于所有的Ax Bx Cx,有 d[Bx] - d[Ax] <= Cx;
      2、对于所有的Ay By Cy,有 d[By] - d[Ay] >= Cy;
      3、然后根据我们的设定,有 d[x] >= d[x-1] + 1 (1 < x <= N)  (这个条件是表示任何两个人的位置不重合)
     而我们需要求的是d[N] - d[1]的最大值,即表示成d[N] - d[1] <= T,要求的就是这个T。
     于是我们将所有的不等式都转化成d[x] - d[y] <= z的形式,如下:
      1、d[Bx]  -  d[Ax]    <=    Cx
      2、d[Ay]  -  d[By]    <=  -Cy
      3、d[x-1] -    d[x]    <=    -1
     对于d[x] - d[y] <= z,令z = w(y, x),那么有 d[x] <= d[y] + w(y, x),所以当d[x] > d[y] + w(y, x),我们需要更新d[x]的值,这对应了最短路的松弛操作,于是问题转化成了求1到N的最短路。
       对于所有满足d[x] - d[y] <= z的不等式,从y向x建立一条权值为z的有向边。
      然后从起点1出发,利用SPFA求到各个点的最短路,如果1到N不可达,说明最短路(即上文中的T)无限长,输出-2。如果某个点进入队列大于等于N次,则必定存在一条负环,即没有最短路,输出-1。否则T就等于1到N的最短路。

      2、区间约束
     【例题2】给定n(n <= 50000)个整点闭区间和这个区间中至少有多少整点需要被选中,每个区间的范围为[ai, bi],并且至少有ci个点需要被选中,其中0 <= ai <= bi <= 50000,问[0, 50000]至少需要有多少点被选中。
      例如3 6 2 表示[3, 6]这个区间至少需要选择2个点,可以是3,4也可以是4,6(总情况有 C(4, 2)种 )。

      这类问题就没有线性约束那么明显,需要将问题进行一下转化,考虑到最后需要求的是一个完整区间内至少有多少点被选中,试着用d[i]表示[0, i]这个区间至少有多少点能被选中,根据定义,可以抽象出 d[-1] = 0,对于每个区间描述,可以表示成d[ bi ]  - d[ ai - 1 ] >= ci,而我们的目标要求的是 d[ 50000 ] - d[ -1 ] >= T 这个不等式中的T,将所有区间描述转化成图后求-1到50000的最长路。
      这里忽略了一些要素,因为d[i]描述了一个求和函数,所以对于d[i]和d[i-1]其实是有自身限制的,考虑到每个点有选和不选两种状态,所以d[i]和d[i-1]需要满足以下不等式:  0 <= d[i] - d[i-1] <= 1   (即第i个数选还是不选)
      这样一来,还需要加入 50000*2 = 100000 条边,由于边数和点数都是万级别的,所以不能采用单纯的Bellman-Ford ,需要利用SPFA进行优化,由于-1不能映射到小标,所以可以将所有点都向x轴正方向偏移1个单位(即所有数+1)。

      3、未知条件约束
      未知条件约束是指在不等式的右边不一定是个常数,可能是个未知数,可以通过枚举这个未知数,然后对不等式转化成差分约束进行求解。
     【例题3】
在一家超市里,每个时刻都需要有营业员看管,R(i)  (0 <= i < 24)表示从i时刻开始到i+1时刻结束需要的营业员的数目,现在有N(N <= 1000)个申请人申请这项工作,并且每个申请者都有一个起始工作时间 ti,如果第i个申请者被录用,那么他会连续工作8小时。
现在要求选择一些申请者进行录用,使得任何一个时刻i,营业员数目都能大于等于R(i)。
       i = 0 1 2 3 4 5 6 ... 20 21 22 23 23,分别对应时刻 [i, i+1),特殊的,23表示的是[23, 0),并且有些申请者的工作时间可能会“跨天”。
       a[i] 表示在第i时刻开始工作的人数,是个未知量
       b[i] 表示在第i时刻能够开始工作人数的上限, 是个已知量
       R[i] 表示在第i时刻必须值班的人数,也是已知量
       那么第i时刻到第i+1时刻还在工作的人满足下面两个不等式(利用每人工作时间8小时这个条件):
       当 i >= 7,        a[i-7] + a[i-6] + ... + a[i] >= R[i]                                     (1)
       当 0 <= i < 7,  (a[0] + ... + a[i]) + (a[i+17] + ... + a[23]) >= R[i]              (2)

       对于从第i时刻开始工作的人,满足以下不等式:
       0 <= i < 24,    0 <= a[i] <= b[i]                                                            (3)
       令 s[i] = a[0] + ... + a[i],特殊地,s[-1] = 0
       上面三个式子用s[i]来表示,如下:
       s[i] - s[i-8] >= R[i]                               (i >= 7)                                      (1)
       s[i] + s[23] - s[i+16] >= R[i]               (0 <= i < 7)                                  (2)
       0 <= s[i] - s[i-1] <= b[i]                     (0 <= i < 24)                                (3)
       
      仔细观察不等式(2),有三个未知数,这里的s[23]就是未知条件,所以还无法转化成差分约束求解,但是和i相关的变量只有两个,对于s[23]的值我们可以进行枚举,令s[23] = T, 则有以下几个不等式:
      
      s[i] - s[i-8] >= R[i]
      s[i] - s[i+16] >= R[i] - T
      s[i] - s[i-1] >= 0
      s[i-1] - s[i] >= -b[i]
      
      对于所有的不等式 s[y] - s[x] >= c,建立一条权值为c的边 x->y,于是问题转化成了求从原点-1到终点23的最长路。
      但是这个问题比较特殊,我们还少了一个条件,即:s[23] = T,它并不是一个不等式,我们需要将它也转化成不等式,由于设定s[-1] = 0,所以 s[23] - s[-1] = T,它可以转化成两个不等式:
      s[23] - s[-1] >= T
      s[-1] - s[23] >= -T
      将这两条边补到原图中,求出的最长路s[23]等于T,表示T就是满足条件的一个解,由于T的值时从小到大枚举的(T的范围为0到N),所以第一个满足条件的解就是答案。
      最后,观察申请者的数量,当i个申请者能够满足条件的时候,i+1个申请者必定可以满足条件,所以申请者的数量是满足单调性的,可以对T进行二分枚举,将枚举复杂度从O(N)降为O(logN)。
五、差分约束题集整理
    最短路
      Shortest Path                      ☆☆     单源最短路
      Shortest Path Problem              ☆☆     单源最短路 + 路径数
      HDU Today                          ☆☆     单源最短路
      Idiomatic Phrases Game             ☆☆     单源最短路
      Here We Go(relians) Again          ☆☆     单源最短路
      find the safest road               ☆☆     单源最短路
      Saving James Bond                  ☆☆     单源最短路
      A strange lift                     ☆☆     单源最短路
      Free DIY Tour                      ☆☆     单源最短路 + 路径还原
      find the safest road               ☆☆     单源最短路(多询问)
      Invitation Cards                   ☆☆     单源最短路
      Minimum Transport Cost             ☆☆     单源最短路 + 路径还原
      Bus Pass                           ☆☆     单源最短路
      In Action                          ☆☆     单源最短路 + 背包
      Choose the best route              ☆☆     单源最短路 + 预处理
      find the longest of the shortest   ☆☆     二分枚举 + 最短路
      Cycling                            ☆☆     二分枚举 + 最短路
      Trucking                           ☆☆     二分枚举 + 最短路
      Delay Constrained Maximum Capacity ☆☆     二分枚举 + 最短路
      The Worm Turns                     ☆☆     四向图最长路
      A Walk Through the Forest          ☆☆     按照规则求路径数
      find the mincost route             ☆☆     无向图最小环
      Arbitrage                          ☆☆     多源最短路
      zz's Mysterious Present            ☆☆     单源最短路
      The Shortest Path                  ☆☆     多源最短路
      Bus System                         ☆☆     单源最短路
      How Many Paths Are There           ☆☆     次短路
      WuKong                             ☆☆     两条最短路的相交点个数为P,要求最大化P
      Shortest Path                      ☆☆     多询问的最短路
      Sightseeing                        ☆☆     最短路和次短路的路径数
      Travel                             ☆☆     最短路径树思想
      Shopping                           ☆☆
      Transit search                     
      Invade the Mars                    
      Circuit Board                      
      Earth Hour                         
      Catch the Theves                   

    差分约束
      Layout                                  差分约束系统 - 最短路模型 + 判负环
      World Exhibition                        差分约束系统 - 最短路模型 + 判负环
      House Man                               差分约束系统 - 最短路模型 + 判负环
      Intervals                               差分约束系统 - 最长路模型 边存储用链式前向星
      King                                    差分约束系统 - 最长路模型 + 判正环
      XYZZY                                   最长路 + 判正环
      Integer Intervals                       限制较强的差分约束 - 可以贪心求解
      THE MATRIX PROBLEM                 ☆     差分约束系统 - 最长路模型 + 判正环
      Is the Information Reliable?            差分约束系统 - 最长路模型 + 判正环      
      Advertisement                           限制较强的差分约束 - 可以贪心求解
      Cashier Employment                      二分枚举 + 差分约束系统 - 最长路模型
      Schedule Problem                        差分约束系统 - 最长路模型
      Candies                            
      Burn the Linked Camp               
      Instrction Arrangement             


No comments:

Post a Comment

Labels

GeeksforGeeks (976) Algorithm (811) LeetCode (654) to-do (599) Review (362) Classic Algorithm (334) Classic Interview (298) Dynamic Programming (263) Google Interview (233) LeetCode - Review (233) Tree (146) POJ (137) Difficult Algorithm (136) EPI (127) Different Solutions (119) Bit Algorithms (110) Cracking Coding Interview (110) Smart Algorithm (109) Math (91) HackerRank (85) Lintcode (83) Binary Search (73) Graph Algorithm (73) Greedy Algorithm (61) Interview Corner (61) Binary Tree (58) List (58) DFS (56) Algorithm Interview (53) Advanced Data Structure (52) Codility (52) ComProGuide (52) LeetCode - Extended (47) USACO (46) Geometry Algorithm (45) BFS (43) Data Structure (42) Mathematical Algorithm (42) ACM-ICPC (41) Jobdu (39) Interval (38) Recursive Algorithm (38) Stack (38) String Algorithm (38) Binary Search Tree (37) Knapsack (37) Codeforces (36) Introduction to Algorithms (36) Matrix (36) Must Known (36) Beauty of Programming (35) Sort (35) Space Optimization (34) Array (33) Trie (33) prismoskills (33) Backtracking (32) Segment Tree (32) Union-Find (32) HDU (31) Google Code Jam (30) Permutation (30) Puzzles (30) Array O(N) (29) Data Structure Design (29) Company-Zenefits (28) Microsoft 100 - July (28) to-do-must (28) Random (27) Sliding Window (27) GeeksQuiz (25) Logic Thinking (25) hihocoder (25) High Frequency (23) Palindrome (23) Algorithm Game (22) Company - LinkedIn (22) Graph (22) Hash (22) Queue (22) DFS + Review (21) TopCoder (21) Binary Indexed Trees (20) Brain Teaser (20) CareerCup (20) Company - Twitter (20) Pre-Sort (20) Company-Facebook (19) UVA (19) Probabilities (18) Follow Up (17) Codercareer (16) Company-Uber (16) Game Theory (16) Heap (16) Shortest Path (16) String Search (16) Topological Sort (16) Tree Traversal (16) itint5 (16) Iterator (15) Merge Sort (15) O(N) (15) Bisection Method (14) Difficult (14) Number (14) Number Theory (14) Post-Order Traverse (14) Priority Quieue (14) Amazon Interview (13) BST (13) Basic Algorithm (13) Codechef (13) Majority (13) mitbbs (13) Combination (12) Computational Geometry (12) KMP (12) Long Increasing Sequence(LIS) (12) Modify Tree (12) Reconstruct Tree (12) Reservoir Sampling (12) 尺取法 (12) AOJ (11) DFS+Backtracking (11) Fast Power Algorithm (11) Graph DFS (11) LCA (11) LeetCode - DFS (11) Ordered Stack (11) Princeton (11) Tree DP (11) 挑战程序设计竞赛 (11) Binary Search - Bisection (10) Company - Microsoft (10) Company-Airbnb (10) Euclidean GCD (10) Facebook Hacker Cup (10) HackerRank Easy (10) Reverse Thinking (10) Rolling Hash (10) SPOJ (10) Theory (10) Tutorialhorizon (10) X Sum (10) Coin Change (9) Divide and Conquer (9) Lintcode - Review (9) Mathblog (9) Max-Min Flow (9) Stack Overflow (9) Stock (9) Two Pointers (9) Book Notes (8) Bottom-Up (8) DP-Space Optimization (8) Graph BFS (8) LeetCode - DP (8) LeetCode Hard (8) Prefix Sum (8) Prime (8) Suffix Tree (8) System Design (8) Tech-Queries (8) Time Complexity (8) Use XOR (8) 穷竭搜索 (8) Algorithm Problem List (7) DFS+BFS (7) Facebook Interview (7) Fibonacci Numbers (7) Game Nim (7) HackerRank Difficult (7) Hackerearth (7) Interval Tree (7) Linked List (7) Longest Common Subsequence(LCS) (7) Math-Divisible (7) Miscs (7) O(1) Space (7) Probability DP (7) Radix Sort (7) Simulation (7) Xpost (7) n00tc0d3r (7) 蓝桥杯 (7) Bucket Sort (6) Catalan Number (6) Classic Data Structure Impl (6) DFS+DP (6) DP - Tree (6) How To (6) Interviewstreet (6) Kadane’s Algorithm (6) Knapsack - MultiplePack (6) Level Order Traversal (6) Manacher (6) Minimum Spanning Tree (6) One Pass (6) Programming Pearls (6) Quick Select (6) Rabin-Karp (6) Randomized Algorithms (6) Sampling (6) Schedule (6) Suffix Array (6) Threaded (6) reddit (6) AI (5) Art Of Programming-July (5) Big Data (5) Brute Force (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Crazyforcode (5) DFS+Cache (5) DP-Multiple Relation (5) DP-Print Solution (5) Dutch Flag (5) Fast Slow Pointers (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Inversion (5) Java (5) Kadane - Extended (5) Matrix Chain Multiplication (5) Microsoft Interview (5) Morris Traversal (5) Pruning (5) Quadtrees (5) Quick Partition (5) Quora (5) SPFA(Shortest Path Faster Algorithm) (5) Subarray Sum (5) Sweep Line (5) Traversal Once (5) TreeMap (5) jiuzhang (5) to-do-2 (5) 单调栈 (5) 树形DP (5) 1point3acres (4) Anagram (4) Approximate Algorithm (4) Backtracking-Include vs Exclude (4) Brute Force - Enumeration (4) Chess Game (4) Company-Amazon (4) Consistent Hash (4) Convex Hull (4) Cycle (4) DP-Include vs Exclude (4) Dijkstra (4) Distributed (4) Eulerian Cycle (4) Flood fill (4) Graph-Classic (4) HackerRank AI (4) Histogram (4) Kadane Max Sum (4) Knapsack - Mixed (4) Knapsack - Unbounded (4) Left and Right Array (4) MinMax (4) Multiple Data Structures (4) N Queens (4) Nerd Paradise (4) Parallel Algorithm (4) Practical Algorithm (4) Pre-Sum (4) Probability (4) Programcreek (4) Quick Sort (4) Spell Checker (4) Stock Maximize (4) Subsets (4) Sudoku (4) Symbol Table (4) TreeSet (4) Triangle (4) Water Jug (4) Word Ladder (4) algnotes (4) fgdsb (4) 最大化最小值 (4) A Star (3) Abbreviation (3) Algorithm - Brain Teaser (3) Algorithm Design (3) Anagrams (3) B Tree (3) Big Data Algorithm (3) Binary Search - Smart (3) Caterpillar Method (3) Coins (3) Company - Groupon (3) Company - Indeed (3) Cumulative Sum (3) DP-Fill by Length (3) DP-Two Variables (3) Dedup (3) Dequeue (3) Dropbox (3) Easy (3) Edit Distance (3) Expression (3) Finite Automata (3) Forward && Backward Scan (3) Github (3) GoLang (3) Include vs Exclude (3) Joseph (3) Jump Game (3) Knapsack-多重背包 (3) LeetCode - Bit (3) LeetCode - TODO (3) Linked List Merge Sort (3) LogN (3) Master Theorem (3) Maze (3) Min Cost Flow (3) Minesweeper (3) Missing Numbers (3) NP Hard (3) Online Algorithm (3) Pascal's Triangle (3) Pattern Match (3) Project Euler (3) Rectangle (3) Scala (3) SegmentFault (3) Stack - Smart (3) State Machine (3) Streaming Algorithm (3) Subset Sum (3) Subtree (3) Transform Tree (3) Two Pointers Window (3) Warshall Floyd (3) With Random Pointer (3) Word Search (3) bookkeeping (3) codebytes (3) Activity Selection Problem (2) Advanced Algorithm (2) AnAlgorithmADay (2) Application of Algorithm (2) Array Merge (2) BOJ (2) BT - Path Sum (2) Balanced Binary Search Tree (2) Bellman Ford (2) Binomial Coefficient (2) Bit Mask (2) Bit-Difficult (2) Bloom Filter (2) Book Coding Interview (2) Branch and Bound Method (2) Clock (2) Codesays (2) Company - Baidu (2) Complete Binary Tree (2) DFS+BFS, Flood Fill (2) DP - DFS (2) DP-3D Table (2) DP-Classical (2) DP-Output Solution (2) DP-Slide Window Gap (2) DP-i-k-j (2) DP-树形 (2) Distributed Algorithms (2) Divide and Conqure (2) Doubly Linked List (2) GoHired (2) Graham Scan (2) Graph - Bipartite (2) Graph BFS+DFS (2) Graph Coloring (2) Graph-Cut Vertices (2) Hamiltonian Cycle (2) Huffman Tree (2) In-order Traverse (2) Include or Exclude Last Element (2) Information Retrieval (2) Interview - Linkedin (2) Invariant (2) Islands (2) Knuth Shuffle (2) LeetCode - Recursive (2) Linked Interview (2) Linked List Sort (2) Longest SubArray (2) Lucene-Solr (2) MST (2) MST-Kruskal (2) Math-Remainder Queue (2) Matrix Power (2) Minimum Vertex Cover (2) Negative All Values (2) Number Each Digit (2) Numerical Method (2) Object Design (2) Order Statistic Tree (2) Palindromic (2) Parentheses (2) Parser (2) Peak (2) Programming (2) Range Minimum Query (2) Reuse Forward Backward (2) Robot (2) Rosettacode (2) Scan from right (2) Search (2) Shuffle (2) Sieve of Eratosthenes (2) SimHash (2) Simple Algorithm (2) Skyline (2) Spatial Index (2) Stream (2) Strongly Connected Components (2) Summary (2) TV (2) Tile (2) Traversal From End (2) Tree Sum (2) Tree Traversal Return Multiple Values (2) Word Break (2) Word Graph (2) Word Trie (2) Young Tableau (2) 剑指Offer (2) 数位DP (2) 1-X (1) 51Nod (1) Akka (1) Algorithm - How To (1) Algorithm - New (1) Algorithm Series (1) Algorithms Part I (1) Analysis of Algorithm (1) Array-Element Index Negative (1) Array-Rearrange (1) Auxiliary Array (1) Auxiliary Array: Inc&Dec (1) BACK (1) BK-Tree (1) BZOJ (1) Basic (1) Bayes (1) Beauty of Math (1) Big Integer (1) Big Number (1) Binary (1) Binary Tree Variant (1) Bipartite (1) Bit-Missing Number (1) BitMap (1) BitMap index (1) BitSet (1) Bug Free Code (1) BuildIt (1) C/C++ (1) CC Interview (1) Cache (1) Calculate Height at Same Recusrion (1) Cartesian tree (1) Check Tree Property (1) Chinese (1) Circular Buffer (1) Code Quality (1) Codesolutiony (1) Company - Alibaba (1) Company - Palantir (1) Company - WalmartLabs (1) Company-Apple (1) Company-Epic (1) Company-Salesforce (1) Company-Snapchat (1) Company-Yelp (1) Compression Algorithm (1) Concurrency (1) Convert BST to DLL (1) Convert DLL to BST (1) Custom Sort (1) Cyclic Replacement (1) DFS-Matrix (1) DP - Probability (1) DP Fill Diagonal First (1) DP-Difficult (1) DP-End with 0 or 1 (1) DP-Fill Diagonal First (1) DP-Graph (1) DP-Left and Right Array (1) DP-MaxMin (1) DP-Memoization (1) DP-Node All Possibilities (1) DP-Optimization (1) DP-Preserve Previous Value (1) DP-Print All Solution (1) Database (1) Detect Negative Cycle (1) Directed Graph (1) Do Two Things at Same Recusrion (1) Domino (1) Dr Dobb's (1) Duplicate (1) Equal probability (1) External Sort (1) FST (1) Failure Function (1) Fraction (1) Front End Pointers (1) Funny (1) Fuzzy String Search (1) Game (1) Generating Function (1) Generation (1) Genetic algorithm (1) GeoHash (1) Geometry - Orientation (1) Google APAC (1) Graph But No Graph (1) Graph Transpose (1) Graph Traversal (1) Graph-Coloring (1) Graph-Longest Path (1) Gray Code (1) HOJ (1) Hanoi (1) Hard Algorithm (1) How Hash (1) How to Test (1) Improve It (1) In Place (1) Inorder-Reverse Inorder Traverse Simultaneously (1) Interpolation search (1) Interview (1) Interview - Easy (1) Interview - Facebook (1) Isomorphic (1) JDK8 (1) K Dimensional Tree (1) Knapsack - Fractional (1) Knapsack - ZeroOnePack (1) Knight (1) Kosaraju’s algorithm (1) Kruskal (1) Kruskal MST (1) Kth Element (1) Least Common Ancestor (1) LeetCode - Binary Tree (1) LeetCode - Coding (1) LeetCode - Detail (1) LeetCode - Related (1) LeetCode Diffcult (1) Linked List Reverse (1) Linkedin (1) Linkedin Interview (1) Local MinMax (1) Logic Pattern (1) Longest Common Subsequence (1) Longest Common Substring (1) Longest Prefix Suffix(LPS) (1) Manhattan Distance (1) Map && Reverse Map (1) Math - Induction (1) Math-Multiply (1) Math-Sum Of Digits (1) Matrix - O(N+M) (1) Matrix BFS (1) Matrix Graph (1) Matrix Search (1) Matrix+DP (1) Matrix-Rotate (1) Max Min So Far (1) Median (1) Memory-Efficient (1) MinHash (1) MinMax Heap (1) Monotone Queue (1) Monto Carlo (1) Multi-Reverse (1) Multiple DFS (1) Multiple Tasks (1) Next Successor (1) Offline Algorithm (1) PAT (1) Parent-Only Tree (1) Partition (1) Path Finding (1) Patience Sort (1) Persistent (1) Pigeon Hole Principle (1) Power Set (1) Pratical Algorithm (1) Probabilistic Data Structure (1) Proof (1) Python (1) Queue & Stack (1) RSA (1) Ranking (1) Rddles (1) ReHash (1) Realtime (1) Recurrence Relation (1) Recursive DFS (1) Recursive to Iterative (1) Red-Black Tree (1) Region (1) Regular Expression (1) Resources (1) Reverse Inorder Traversal (1) Robin (1) Selection (1) Self Balancing BST (1) Similarity (1) Sort && Binary Search (1) String Algorithm. Symbol Table (1) String DP (1) String Distance (1) SubMatrix (1) Subsequence (1) System of Difference Constraints(差分约束系统) (1) TSP (1) Ternary Search Tree (1) Test (1) Thread (1) TimSort (1) Top-Down (1) Tournament (1) Tournament Tree (1) Transform Tree in Place (1) Tree Diameter (1) Tree Rotate (1) Trie + DFS (1) Trie and Heap (1) Trie vs Hash (1) Trie vs HashMap (1) Triplet (1) Two Data Structures (1) Two Stacks (1) USACO - Classical (1) USACO - Problems (1) UyHiP (1) Valid Tree (1) Vector (1) Wiggle Sort (1) Wikipedia (1) Yahoo Interview (1) ZOJ (1) baozitraining (1) codevs (1) cos126 (1) javabeat (1) jum (1) namic Programming (1) sqrt(N) (1) 两次dijkstra (1) 九度 (1) 二进制枚举 (1) 夹逼法 (1) 归一化 (1) 折半枚举 (1) 枚举 (1) 状态压缩DP (1) 男人八题 (1) 英雄会 (1) 逆向思维 (1)

Popular Posts