差分约束系统（例题：ccf-再卖菜）

爱被打了一巴掌 2022-04-05 09:50 228阅读 0赞

### 一、差分约束系统是啥？ ###

差分约束系统（system of difference constraints），是求解关于一组变数的特殊不等式组之方法。如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如xj-xi<=bk(i,j∈\[1,n\],k∈\[1,m\]),则称其为差分约束系统(system of difference constraints)。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。

通俗一点地说，差分约束系统就是一些不等式的组，而我们的目标是通过给定的约束不等式组求出最大值或者最小值或者差分约束系统是否有解。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTcyNTA1_size_16_color_FFFFFF_t_70]

### 二、差分约束系统求解 ###

差分约束系统可以转化为图论来解决，对应于上面的不等式组，如果要求出x3-x0的最大值的话，叠加不等式可以推导出x3-x0<=7,最大值即为7，我们可以通过建立一个图，包含6个顶点，**对每个xj-xi<=bk，建立一条i到j的有向边，权值为bk**。通过求出这个图的x0到x3的最短路可以知道也为7，这是巧合吗？并不是。

之所以差分约束系统可以通过图论的最短路来解，**是因为xj-xi<=bk，会发现它类似最短路中的三角不等式d\[v\] <=d\[u\]+w\[u,v\]，即d\[v\]-d\[u\]<=w\[u,v\]**。而求取最大值的过程类似于最短路算法中的松弛过程。

### 三、差分约束的应用以及变形 ###

差分约束系统的应用很广，都会有一定的背景，我们只需要根据题意构造出差分约束系统，然后再根据题目的要求求解就行了。

一般题目会有三种情况：(1)、求取最短路 (2)、求取最长路 (3)、判断差分约束系统的解是否存在

当然这三种也可能会相互结合  
差分约束系统的解法如下：

1、 根据条件把题意通过变量组表达出来得到不等式组，注意要发掘出隐含的不等式，比如说前后两个变量之间隐含的不等式关系。

2、 进行建图：  
首先根据题目的要求进行不等式组的标准化。

(1)、如果**要求取最小值，那么求出最长路**，那么将不等式**全部化成xi – xj >= k的形式**，这样**建立j->i的边，权值为k的边**，**如果不等式组中有xi – xj > k，因为一般题目都是对整形变量的约束，化为xi – xj >= k+1**即可，如果xi – xj = k呢，那么可以变为如下两个：xi – xj >= k, **xi – xj <= k,进一步变为xj – xi >= -k**，建立两条边即可。

(2)、如果**求取的是最大值，那么求取最短路**，**将不等式全部化成xi – xj <= k的形式, 这样建立j->i的边，权值为k的边**，如果像上面的两种情况，那么同样地标准化就行了。

(3)、如果要判断差分约束系统是否存在解，一般都是判断环，选择求最短路或者最长路求解都行，只是不等式标准化时候不同，判环地话，用**spfa即可，n个点中如果同一个点入队超过n次，那么即存在环。**

值得注意的一点是：建立的图可能不联通，我们只需要加入一个超级源点，比如说求取最长路时图不联通的话，我们只需要加入一个点S，对其他的每个点建立一条权值为0的边图就联通了，然后从S点开始进行spfa判环。最短路类似。

3、 建好图之后直接spfa或bellman-ford求解，不能用dijstra算法，因为一般存在负边，注意初始化的问题。

**例题ccf-再卖菜**  
分析及思路：  
这道题是非常经典的最短路解差分约束问题  
如何建图呢 ？  
首先这里的不等式是这样的：  
假设n=5，则有：

a1* 2≤ x1+x2 ≤ a1* 2+1
    a2* 3≤ x1+x2+x3 ≤ a2* 3+2
    a3* 3≤ x2+x3+x4 ≤ a3* 3+2
    a4* 3≤ x3+x4+x5 ≤ a4* 3+2
    a5* 2≤ x4+x5 ≤ a5* 2+1
    x1≥1
    x2≥1
    x3≥1
    x4≥1
    x5≥1

xi为第一天第i家店的售价，ai为第二天第i家点的售价。  
不难发现存在3元一次不等式怎么办呢？我们可以引入中间变量si=x0+x1+…+xi,这里的x0等于0;  
即可将上面的第一个不等式转化成： a1\* 2≤ s2-s0 ，a1\* 2+1≤s0-s2.其它的也一样，不一一列举，全部转化成大于等于的形式，sj-si≥k，i到j建立一条权值为k的单向边，然后spfa跑最长路即可，这里的spfa与原来的spfa有些区别，在spfa之前记得将所有点加入队列，并且dist置0，因为差分约束系统不保证图是连通的，所以要先建立一个虚拟节点，这个虚拟节点为源点，向所有边连接一条权值为0的有向边，以上的操作便是人工省略了虚拟源点的步骤。

AC代码：

#include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cmath>
    #include <cstring>
    #include <vector>
    #include <queue>
    
    using namespace std;
    
    const int MAXN = 350;
    
    struct node{
        int val;
        int v;
        node(){}
        node(int _v, int _val):v(_v),val(_val){}
    };
    
    int n;
    vector<node> G[MAXN];
    int a[MAXN],dis[MAXN],vis[MAXN],inq[MAXN];
    
    void spfa(){
        queue<int> q;
        q.push(0);
        vis[0] = 1;
        while(!q.empty()){
            int u= q.front();
            q.pop();
            vis[u] = 0;
            inq[u]++;
            for(int i=0; i<G[u].size(); ++i){
                int v = G[u][i].v;
                if(dis[v] < dis[u] + G[u][i].val){
                    dis[v] = dis[u] + G[u][i].val;
                    if(!vis[v]){
                        vis[v] = 1;
                        q.push(v);
                    }
                   
                }
            }
        }
    }
    
    int main(int argc, char const *argv[])
    {
        
       
        cin>>n;
        for(int i=1; i<=n; ++i){
            cin>>a[i];
        }
    
        for(int i=0; i<n-2; ++i){
            G[i].push_back(node(i+3,a[i+2]*3));
            G[i+3].push_back(node(i,-(a[i+2]*3+2)));
        }
    
        G[0].push_back(node(2,a[1]*2));
        G[2].push_back(node(0,-(a[1]*2+1)));
        G[n-2].push_back(node(n,a[n]*2));
        G[n].push_back(node(n-2,-(a[n]*2+1)));
    
        for(int i=1; i<=n; ++i) G[i-1].push_back(node(i,1));
    
        memset(dis, 0, sizeof(dis));
        memset(vis, 0, sizeof(vis));
        memset(inq, 0, sizeof(inq));
    
        spfa();
    
        a[1] = dis[1];
        for(int i=2; i<=n; ++i) a[i] = dis[i] - dis[i-1];
    
        cout<<a[1];
        for(int i=2; i<=n; ++i) cout<<" "<<a[i];
        cout<<endl;
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTcyNTA1_size_16_color_FFFFFF_t_70]: /images/20220405/b4d21b0b3c454e45aa1d86af3c598ca9.png