差分约束系统是很多问题求解的模型，这一类问题可以转化为图的单源最短路径问题。

        所谓差分约束系统是指如下的若干不等式组成的约束系统：

        这里的$x_i,x_j$均为变量，w为常数。不等式组要么无解要么有无数种解，这是因为如果存在一组解，易知它们分别加上同样的数d得到的仍是一组解。
        将不等式变形：

        发现这与单源最短路径的松弛操作十分类似：

        由此可知，如果将每一个变量看做点，不等关系看做边建图，求单源最短路径，它们的最短路径值一定满足所有的不等关系。这样差分约束问题就可以转化为图的单源最短路径问题。对于不等式$x_i-x_j\leq w$，需要建立j到i，边权为w的有向边。
        源点如何找呢？我们需要引入一个新变量$x_0$，并建立$x_0$到其余所有变量的有向边，边权为0，这样相当于加了下面几个约束关系：

        显然加入这些不等式不会影响原不等式的实际结果，可以认为$x_0$是所有变量的上界。这样以$x_0$为源点求单源最短路径即可。在求单源最短路径时，通常令源点的路径长即dict[0]=0，这样相当于规定了$x_0=0$，所有变量的取值便成为非正数。同样地，如果规定dict[0]=p，这样所有变量取值都不会超过p。源点的dict值可以作为变量取值的上界。
        不等式组的无解判定：当单源最短路不存在时（即图中有负环），不等式组无解。基于此，常常用SPFA解决差分约束问题。
        另外，当不等式给出$x_i-x_j\geq w$形式不等式时，两边乘一个-1，即可化为标准形式。如果给出$x_i-x_j<w$形式，可以化为$x_i-x_j\leq w-1$（因为变量取值通常只取整数）。$x_i-x_j=w$可以化为$x_i-x_j\geq w$和$x_i-x_j\leq w$两个不等式。
        最终得出的解只是一组特解，这组特解不一定符合题意，通常需要将所有值同时加上合适的d来使它们都达到合理的范围。
        差分约束还有另一种解决方法，就是求最长路，这种方法针对形如$x_i-x_j\geq w$的方程。仍然建立j到i边权为w的有向边，但是要求最长路，此时dict[0]是所有变量的下界。求最长路方法与最短路类似，都用SPFA算法。无解判定：当图中存在正权环时无解。
        例题：HDU1384 Intervals
        一道裸的差分约束题目。规定$d_i$为0~i中已经被选的数的个数，那么可以列出不等式：

        解决此类问题时需要善于找到隐藏不等关系，比如每一个数最多选一次，因此还有：

        建图跑最短（长）路即可，然后找到最小的合法解。题目特点决定了差分约束系统一定有解，不用判定无解情况。另外注意这题有多组测试样例，题干中未提及。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<iostream>
#include<cstdio>
#include<queue>

#define MAX (50000+5)
#define inf (int)1e9
using namespace std;
struct {
    int to, next, v;
} edge[MAX * 4 + 10000];
int head[MAX], cnt = 1, vis[MAX] = {0}, n, a[MAX], b[MAX], c[MAX], dict[MAX], minn, maxn;

inline void add(int x, int y, int z) {//建边
    edge[cnt].to = y, edge[cnt].next = head[x], edge[cnt].v = z, head[x] = cnt++;
}

queue<int> que;

int main() {
    ios::sync_with_stdio(false);
    while (cin >> n) {
        cnt = 1, minn = inf, maxn = -inf;
        for (int i = 0; i <= 50002; i++)dict[i] = inf, head[i] = -1, vis[i] = 0;
        for (int i = 1; i <= n; i++) {
            cin >> a[i], cin >> b[i], cin >> c[i];
            a[i] += 2, b[i] += 2;
            add(b[i], a[i] - 1, -c[i]), maxn = max(maxn, b[i]), minn = min(minn, a[i] - 1);
        }
        for (int i = 2; i <= maxn; i++)add(i - 1, i, 1), add(i, i - 1, 0);//补充约束关系
        dict[0] = 0;
        for (int i = 1; i <= maxn; i++)add(0, i, 0);//补充x0
        que.push(0), vis[0] = 1;
        while (!que.empty()) {//SPFA算法
            int p = que.front();
            que.pop(), vis[p] = 0;
            for (int i = head[p]; ~i; i = edge[i].next) {
                if (dict[edge[i].to] > dict[p] + edge[i].v) {
                    dict[edge[i].to] = dict[p] + edge[i].v;
                    if (!vis[edge[i].to])que.push(edge[i].to), vis[edge[i].to] = 1;
                }
            }
        }
        cout << -dict[minn] << endl;
    }
    return 0;
}