差分约束系统

参考：https://www.cnblogs.com/genius777/p/9163103.html

差分约束系统只是对最短路算法的一种应用，没有什么新的算法，只是对于具体问题的建图方法的确定

差分约束系统解决的问题是不等式组的求解：

X1 - X2 <= 0
X1 - X5 <= -1
X2 - X5 <= 1
X3 - X1 <= 5
X4 - X1 <= 4
X4 - X3 <= -1
X5 - X3 <= -3
X5 - X4 <= -3

这就是一个不等式组，给出的不等式组只存在小于等于号，如果有个别的式子是大于等于，我们可以通过两边同时乘-1的得到统一的不等号方向的不等式组。

这个不等式组一定是无解和无数解两种情况，因为如果是存在任意一组解，{x1,x2,x3,x4,x5},我们都可以通过{x1+k,x2+k,x3+k,x4+k,x5+k}得到一个新的解。所以解的个数是无数的。

因为每个数都加k，他们任意两个数之间的差是不变的，所以对于不等式没有影响。

与最短路联系

B - A <= c     (1)
C - B <= a     (2)
C - A <= b     (3)

如果要求C-A的最大值，可以知道max（C-A）= min(b,a+c),而这正对应了下图中C到A的最短路。

差分约束建图技巧

1.对于一个全部都是<=号的不等式组，我们可以将每个式子转化为Xi<=Xj+W(i,j),那么就建一条边，Xj->Xi=W(i,j),然后利用最短路径解决问题，在x0定死的情况下，求得最小值

2.对于一个全部都是>=号的不等式组，我们可以将每个式子转化为Xi>=Xj+W(i,j),那么就建一条边，Xj->Xi=W(i,j),然后利用最长路径解决问题，在x0定死的情况下，求得最大值

如果dis[Xi]为inf或-inf,那么Xi为任意解

如果求最短路的过程中出现负环，那么说明该不等式组无解

题目描述

需要放置n头牛，AL和BL两头牛之间存在“喜欢”关系，则它们之间的距离不能超过DL，有些AD和BD两头牛之间存在“不喜欢”关系，则它们之间的距离不能超过DD。所有牛编号从1~N，求1号牛和N号牛之间的最大距离，无解输出-1，距离无限大输出-2

分析

根据条目分析，可以得出约束条件为，d[i]为第i头牛放置的位置

• d[i+1] + 0 >= d[i]，n头牛按编号顺序依次放置，且可放置在同一位置
• d[AL] + DL >= d[BL]，“喜欢”关系的两头牛之间距离不超过DL
• d[BD] - DD >= d[AD]，“不喜欢”关系两头牛之间的距离不小于DD

将原问题转化成最短路问题，

• 建立一条从i+1到i，权值为0的边
• 建立一条从AL到BL，权值为DL的边
• 建立一条从BD到AD，权值为-DD的边

原问题d[N] - d[1]的最大值，对应顶点1到顶点N的最短距离（不理解可看上文差分约束与最短路径关系部分），由于图中存在负权重的边，不能使用Dijkstra算法，可采用Bellman-Ford算法求解。

代码

#include <stdio.h>
#include <iostream>
#include <climits>
#include <vector>
using namespace std;

const int MAXN = 1000 + 10;
const int MAXM = 10000 + 10;
const int INF = INT_MAX;

int N, ML, MD;
int AL[MAXM], BL[MAXM], DL[MAXM];   //'喜欢'关系约束
int AD[MAXM], BD[MAXM], DD[MAXM];   //'不喜欢'关系约束
int dist[MAXN];     //最短距离

//邻接表存储图
struct Edge{
    int to, weight;
    Edge(int t, int w): to(t), weight(w) {}
};
vector<Edge> G[MAXN];

//根据差分约束建立图
void BuildGraph(){
    //从i+1->i权值为0的边
    for (int i = 1; i < N; ++i) {
        G[i+1].push_back(Edge(i, 0));
    }

    /*
         * BL - AL <= DL
         * AL + DL >= BL
         * 从AL到BL权值为DL的边 */
    for (int i = 0; i < ML; ++i) {
        G[AL[i]].push_back(Edge(BL[i], DL[i]));
    }

    /*
         * BD - AD >= DD
         * BD - DD >= AD
         * 从BD到AD权值-DD的边*/
    for (int i = 0; i < MD; ++i) {
        G[BD[i]].push_back(Edge(AD[i], -DD[i]));
    }
}

void Bellman_Ford(){
    fill(dist, dist + MAXN, INF);
    dist[1] = 0;

    //循环N-1次
    for (int i = 0; i < N - 1; ++i) {
        //对所有边进行松弛操作
        for (int j = 1; j <= N; ++j) {
            for (int k = 0; k < G[j].size(); ++k) {
                Edge e = G[j][k];
                if (dist[j] < INF && dist[e.to] > dist[j] + e.weight){
                    dist[e.to] = dist[j] + e.weight;
                }
            }
        }
    }

    //再遍历一次所有边（第N次循环）
    bool ngloop = false;
    for (int j = 1; j <= N; ++j) {
        for (int k = 0; k < G[j].size(); ++k) {
            Edge e = G[j][k];
            //如果本次有更新，则存在负环
            if (dist[j] < INF && dist[e.to] > dist[j] + e.weight){
                dist[e.to] = dist[j] + e.weight;
                ngloop = true;
            }
        }
    }

    if (ngloop){
        printf("-1\n");
    }
    else{
        int ans = dist[N];
        if (ans == INF){
            ans = -2;
        }
        printf("%d\n", ans);
    }
}

int main(){
    scanf("%d%d%d", &N, &ML, &MD);
    for (int i = 0; i < ML; ++i) {
        scanf("%d%d%d", &AL[i], &BL[i], &DL[i]);
    }
    for (int i = 0; i < MD; ++i) {
        scanf("%d%d%d", &AD[i], &BD[i], &DD[i]);
    }

    BuildGraph();

    Bellman_Ford();

    return 0;
}