差分约束
什么是差分约束？
差分约束系统（system of difference constraints），是求解关于一组变数的特殊不等式组之方法。如果一个系统由n个变量和m个约束条件组成，其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束系统(system of difference constraints)。亦即，差分约束系统是求解关于一组变量的特殊不等式组的方法。
（以上转自某博客）
其实。。差分约束在某种程度上来说像是一个转换的工具，解释请看下文
差分约束的核心思路
差分约束大部分时候像是把一个问题转换为几个不等式，并转换为最短路来求解
如何转换为最短路？
我们用到了三角不等式。
B - A <= c (1)
C - B <= a (2)
C - A <= b (3)
如果要求C-A的最大值，可以知道max（C-A）= min(b,a+c)
如：对于一个 xi-xj<=an
则有一条i到j的边，权值为an。以此来建图。
有些时候不等式不是现成的，这是需要对现有的不等式进行加减。如
x3-x2<=1
x2-x1<=3
可以将两式相加，得到新的不等式
（三角不等式也被经常用来做最短路的松弛操作）
最长路&最短路
最长路
最长路就是第一个点到第n个点的最短路
证明可以另查（实际上我也不会证）
但是你可以这么理解
对于一个式子a-b，当a一定，b越小，这个式子的值越大
最短路
最短路其实和最长路相反，是第一个点到第n个点的最长路
证明方法同上理（就是b大了，a-b的值就小了）
判断有没有解
就是用spfa来判环
（据说优化后的bellman-ford也可以)
干货版（转自其他博客）
上面的是我通俗化过的，但是如果你想看看最正式的解释也是可以的
下面有一个超级源点，其实就是在处理特例
差分约束系统的解法如下：
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算法，因为一般存在负边，注意初始化的问题。
程序实现
其实你可以去看看poj的1201-intervals。这道题被许多博客当做范例来讲，感觉也确实像是一个模版题。可以试试。
附上不是我的标程一个（主要是poj最近打不开）
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn= 50000+10;
const int maxm=500000+10;
#define INF 1e9
struct Edge
{
int from,to,dist;
Edge(){}
Edge(int f,int t,int d):from(f),to(t),dist(d){}
};
struct SPFA
{
int n,m;
int head[maxn],next[maxm];
Edge edges[maxm];
int d[maxn];
bool inq[maxn];
void init()
{
m=0;
memset(head,-1,sizeof(head));
}
void AddEdge(int from,int to,int dist)
{
edges[m]=Edge(from,to,dist);
next[m]=head[from];
head[from]=m++;
}
int spfa()
{
memset(inq,0,sizeof(inq));
for(int i=0;i<n;i++) d[i]= i==0?0:INF;
queue<int> Q;
Q.push(0);
while(!Q.empty())
{
int u=Q.front(); Q.pop();
inq[u]=false;
for(int i=head[u];i!=-1;i=next[i])
{
Edge &e=edges[i];
if(d[e.to]>d[u]+e.dist)
{
d[e.to]=d[u]+e.dist;
if(!inq[e.to])
{
inq[e.to]=true;
Q.push(e.to);
}
}
}
}
return d[n-1]-d[9];
}
}SP;
int main()
{
int n,max_v=-1;
scanf("%d",&n);
SP.init();
while(n--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
b+=10,a+=10;//所有值都加10了,以免a-1成为-1
max_v=max(max_v,b);
SP.AddEdge(b,a-1,-c);
}
for(int i=10;i<=max_v;i++)//从该循环可看出,本差分约束的点编号为:[9,max_v](未包含超级源0号点)
{
SP.AddEdge(i,i-1,0);
SP.AddEdge(i-1,i,1);
SP.AddEdge(0,i,0);
}
SP.AddEdge(0,9,0);
SP.n=max_v+1;
printf("%d\n",SP.spfa());//注意最终结果是d[max_v]-d[9]的值,而不是d[max_v]的单独值
return 0;
}
思路还是一样的，只是感觉这个代码写的。。不是很通俗易懂
差分约束就到这里了，我觉得它更像一个工具，有种数形结合百般好的感觉
