差分约束

/*

差分约束系统
{
    x1-x2<=c1
    x3-x4<=c2
    x5-x6<=c3
    ...
}


我们对于每个x1-x2<=c 可以把它转化成x1<=x2+c 这和最短路不等式中的d[u]<=d[v]+c有相似之处
利用这一点,我们可以将其转化为图论问题
也就是说,对于每个Xn-1-Xn<=C 我们可以建一条由Xn->Xn-1的长度为C的边,然后跑一遍最短路来求解不等式组


差分约束题型概览
First.求解不等式组是否有可行解

1.先将每个不等式xi<=xj+k,转化成一条从xj->xi长度为k的边
2.然后找到一个超级源点使得其可以遍历到所有边
3.从该源点求一遍最短路

result1:如果存在负环,则不等式一定无解
result2:如果没有负环,则d[i]就是原不等式的一组可行解

浅浅解释一下:1.如果存在负环,也就是说对于一个点i来说,我们可以从i点遍历回i且回路总权值为负数
              假设此环为i->t-n....->t-2->t-1->t->i
              那么将这个环转化成不等式就是
              {
                  Xt-n<=Xi+Wt-n-1
                  ....
                  Xt-1<=Xt-2+Wt-2
                  Xt<=Xt-1+Wt-1
                  Xi<=Xt+Wt
              }

              将这个不等式整理可得Xi<=Xt+Wt<=Xt-1+Wt+Wt-1<=Xt-2+Wt+Wt-1+Wt-2<=Xi+Wt+Wt-1+...+Wt-n-1
              因为是一个负环,所以Xi<=Xi+c(c<0),不合法,所以不等式一定无解

            2.因为我们可以遍历到每条边,所以对于每条边来说都一定满足d[i]<=d[j]+c
              也就是说每个点的d都是满足跟这个点相关的所有不等式的条件的
              所以如果建的图可以求出每个点的最短距离d[i],那么这个d[i]一定是原不等式组的可行解

Second. 求解不等式组满足条件的最大值或者最小值

结论:如果求的是最小值,应该用最长路;如果求最大值,应该用最短路

求x的最大值
求所有从xi出发,构成的多个形如如下的不等式链
xi<=xj+c1<=xk+c2+c1<=.....<=x0+c1+c2+...+cm
最终xi的最大值等于所有上界的最小值

求x的最小值则完全相反
这里的不等式链
xi>=cj+c1>=xk+c2+C1>=...>=x0+c1+c2+...+cm
最终xi的最小值等于所有上界的最大值

tips:如何转化xi<=c,其中c是一个常数
方法:建立一个超级源点0,然后建立0->i的边,长度是c即可

*/


题目分享1
acwing 1169 糖果

条件提取 X=1 Xa == Xb -> Xa >= Xb , Xb <= Xa   b->a, w=0 a->b w=0 
        X=2 Xa < Xb -> Xa + 1 <= Xb      a->b,w=1
        X=3 Xa >= Xb   b->a,w=0
        X=4 Xa > Xb -> Xa >= Xb + 1 b->a,w=1  
        X=5 Xa <= Xb a->b,w=0

    每个小朋友都要分到糖果,也就是xi>=1,所以我们可以从0向每个点连一条长度为1的边

/*

    for(int i=0;i<m;i++)
    {
        int op,a,b;
        scanf("%d%d%d",&op,&a,&b);
        if(op==1) add(a,b,0),add(b,a,0);
        else if(op==2) add(a,b,1);
        else if(op==3) add(b,a,0);
        else if(op==4) add(b,a,1);
        else if(op==5) add(a,b,0);
    }


*/

题目分享2 
acwing 362 区间

求最长路
用s[i]来表示0~i的每个数的出现次数 

s[5]=3 1~5 中的数 

不等关系 
    a[i]<=x<=b[i]的整数x不少于c[i]个     1.s[b[i]]-s[a[i]-1]>=c[i] -> s[b[i]]>=s[a[i]-1]+c[i]

                                         //求前缀和:把0~50000映射成1~50001
                                         s[b[i]+1]>=s[a[i]]+c[i] 
                                        2.s[i]>=s[i-1]
                                        3.s[i-1]>=s[i]-1

题目分享3

acwing 1170 排队布局

求最短路
这里1~i号奶牛是从小到大排序 所以s[i]<=s[i+1]
好感奶牛 s[b]-s[a]<=l s[b]<=s[a]+l 
反感奶牛 s[b]-s[a]>=d s[a]<=s[b]+(-d)
/*先检验是否存在负环 存在 puts("-1);
                    不存在 如果d[n]=0x3f3f3f3f 意味着1~n间没有边 puts("-2")
                               否则            cout<<d[n]<<'\n';*/
###