据说差分约束有很多种，但是我学过的只有SPFA求差分；
我们知道，例如 A-B<=C，那么这就是一个差分约束。
比如说，著名的三角形差分约束，这个大家都是知道的，什么两边之差小于第三边啦，等等等等。
所以说，我们学他干嘛（我们得出结论：学他没用，谢谢大家观看）
咳咳——说正事，我们来看一道例题：【luoguP1993】小K的农场：
题目描述
小K在MC里面建立很多很多的农场，总共n个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共m个），以下列三种形式描述：
- 农场a比农场b至少多种植了c个单位的作物，
- 农场a比农场b至多多种植了c个单位的作物，
- 农场a与农场b种植的作物数一样多。
但是，由于小K的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。
输入格式：
第一行包括两个整数 n 和 m，分别表示农场数目和小 K 记忆中的信息数目。
接下来 m 行：
如果每行的第一个数是 1，接下来有 3 个整数 a,b,c，表示农场 a 比农场 b 至少多种植了 c 个单位的作物。
如果每行的第一个数是 2，接下来有 3 个整数 a,b,c，表示农场 a 比农场 b 至多多种植了 c 个单位的作物。如果每行的第一个数是 3，接下来有 2 个整数 a,b，表示农场 a 种植的的数量和 b 一样多。
输出格式：
如果存在某种情况与小 K 的记忆吻合，输出“Yes”，否则输出“No”。
我们看一看题干，能够发现一些条件：1.A-B>=C，2.A-B<=C，3.A=B。
我们一个一个分析先分析第2个（为什么？等会就明白了）
题中让我们求得是否能够让条件成立，那么就用到我们的SPFA了，怎么用？
还记得SPFA那个更新条件吗
dis[y]>dis[x]+edge[i].w;所以说，让我们反想一下，既然我们求得答案，那么我们肯定想
dis[y]<=dis[x]+edge[i].w
因为这样最后我们就可以求得答案了；
那么如果我们将它推论到差分系统呢，我们想让它成立，那么就要让他限制于一个条件，那么很容易就能懂C应该是edge[i].w;
那么我们推一下，A<=B+C -> A-B<=C。这样我们建一个由B指向A的边，边权为C，那么我们再来看第一个条件就很容易懂了。
这个就直接说了，B-A<=-C，之后就和前面的一样了；
那么来看最后一个条件：A=B。这个应该是初中（应该不是的小学吧QWQ）数学的知识，A>=B && A<=B，就可以实现这个条件的差分替换了;
那么再用上SPFA的judge负环的骚操作就可以了。
这样应该就能写出来这道题了——吗?
你会发现你从1点开始跑会有70分，（其实是水的），为什么呢？
这是因为图可能并不联通，那么你这样跑就会凉凉，那么我们可以建一个超级原点，这样就可以联通了，提交发现60分
！！！怎么还少了QAQ！！！
所以说上面的过程是水的呀，我们会T掉，因为BFS会一直在圈里跑，而圈子又太大，那么SPFA的诟病就出来了（关于SPFA，它死了）
SPFA还没有凉透，因为我们会出现负环，而题中就让我们判断负环，我们没法用其他算法啊！
那么就有了应运而生的SPFA-DFS判负环版本，来看一下代码
bool SPFA(int x){
vis[x]=;//标记在搜索过程中
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(dis[y]>dis[x]+edge[i].w){
dis[y]=dis[x]+edge[i].w;
if(vis[y]) return true;/*循环环出现，也就是负权值不停更新
，那么我们用这个机制就可以return了*/
if(SPFA(y)) return true;
}
}
vis[x]=;//清除标记
return false;//条件成立
}
这样就不会TLE了；
现在来看完整代码（其中有BFS的TLE代码）：
Code
#include<bits/stdc++.h>
#define maxn 10007
using namespace std;
int n,m,head[maxn],cent,vis[maxn],dis[maxn],num[maxn];
struct node{
int next,to,w;
}edge[maxn<<];
queue<int >q; void add(int u,int v,int w){
edge[++cent]=(node){head[u],v,w};head[u]=cent;
} //bool SPFA(int x){
// vis[x]=1,num[x]++,dis[x]=0;
// q.push(x);
// while(!q.empty()){
// int x=q.front();vis[x]=0;q.pop();
// for(int i=head[x];i;i=edge[i].next){
// int y=edge[i].to;
// if(dis[y]>dis[x]+edge[i].w){
// dis[y]=dis[x]+edge[i].w;
// if(!vis[y]){
// q.push(y);
// num[y]++;
// }
// if(num[y]>=n){
// return true;
// }
// }
// }
// }
// return false;
//} bool SPFA(int x){
vis[x]=;//标记在搜索过程中
for(int i=head[x];i;i=edge[i].next){
int y=edge[i].to;
if(dis[y]>dis[x]+edge[i].w){
dis[y]=dis[x]+edge[i].w;
if(vis[y]) return true;/*循环环出现，也就是负权值不停更新
，那么我们用这个机制就可以return了*/
if(SPFA(y)) return true;
}
}
vis[x]=;//清除标记
return false;//条件成立
} int main(){
// freopen("cin.in","r",stdin);
// freopen("cout.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=,s,a,b,c;i<=m;i++){
scanf("%d%d%d",&s,&a,&b);
if(s==){
scanf("%d",&c);
add(a,b,-c);
}else if(s==){
scanf("%d",&c);
add(b,a,c);
}else if(s==){
add(a,b,);
add(b,a,);
}
}
for(int i=;i<=n;i++) add(,i,);//超级源点
memset(dis,0x3f3f3f,sizeof(dis));
dis[]=;//搜索初始化
if(SPFA()) printf("No");
else printf("Yes");
return ;
}
这道题就结束了，再送一道福利题[USACO05DEC]
好了，就这样了。