定义

如果一个系统由 $n$ 个变量 $a_1,a_2...a_n$ 和 $m$ 个约束条件组成，每个约束条件均为形如 $a_i-a_j \leq k$ 的不等式$（i,j∈[1,n] k$为常数），则称其为​差分约束系统​。

换句话说，差分约束系统是求解关于一组变量的特殊不等式组的方法。

（以上内容摘编自百度百科)

算法详解

看到这个不等式，或许你会有点懵，我们先简单变个形：

∵$a_i-a_j<=k$ ∴$a_i<=a_j+k$

现在将 $m$ 个约束条件分成 $n$ 组，$a_i \leq a_j+k$ 属于第 $i$组。

单独考虑第 $i$ 组，设第 $i$ 组共有 $x$ 个条件，每个条件的 $j$ 依次等于$b_1,b_2...b_x$，每个条件的 k 依次等于 $c_1,c_2...c_x$。（即这 $x$ 个条件分别为 $a_i \leq a_{b1}+c_1,...,a_i \leq a_{bx}+c_x$）

那么第 $i$ 组条件就等价于：

考虑

我们突然发现这是一个最短路的形式 -- 具体来说，$b_j$ 向 $i$ 连一条长度为 $c_j$ 的边，$b_i$ 为起点到 $i$ 的最短路径距离，那么上述等式就相当于用点 $b_j$ 去更新$i$。（j∈{1,2,⋯ ,x}

我们回到一开始的式子 $a_i \leq a_j +k$，根据上述分析，我们可以将其转化为从 $j$ 到 $i$ 的一条长度为 $k$ 的边，那么 $a_i$ 就转化成了源点到 $i$ 的最短路径距离。

上述不等式组显然有可能无解，那么怎么判定无解呢？

由于 $a_i$ 是一组最短路的解，那么只需判定最短路是否无解即可。

什么，你不知道如何判定最短路无解？

当然是判负环呀！

具体来说，如果不存在负环，Bellman-Ford 在 $n$ 次松弛后就该结束了，所以只需要​再尝试松弛一次​，如果多的这一次松弛成功，说明有负环，无解；否则有解。

再说说 SPFA 判负环，道理其实是一样的。你每次将一个点丢进队列里，相当于是对这一个点的所有出边进行松弛，那么只需要​记录每个点的进队次数​，若超过 $n$，说明松弛次数太多，有负环，无解；否则有解。

最短路

#include<bits/stdc++.h>
using namespace std;
const int N=5010,M=10010;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
int cnt[N],q[N];
bool st[N];
int dist[N];
void add(int a,int b,int c)
{
	e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
bool spfa() //判断是否存在负环
{
	queue<int> q;
	memset(dist,0x3f,sizeof dist);
	dist[0]=0;
	q.push(0);
	st[0]=1;
	while(q.size())
	{
		int t=q.front();
		q.pop();
		st[t]=0;
		for(int i=h[t];i!=-1;i=ne[i])
		{
			int j=e[i];
			if(dist[j]>dist[t]+w[i]) //距离可以变小
			{
				dist[j]=dist[t]+w[i];
				cnt[j]=cnt[t]+1;
				if(cnt[j]>=n+1) return false;
				if(!st[j])
				{
					q.push(j);
					st[j]=1;
				}
			}
		}
	}
	return true;
}
int main()
{
	scanf("%d%d",&n,&m);
	memset(h,-1,sizeof h);
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		add(b,a,c); //dist[a]<=dist[b]+c
	}
	for(int i=1;i<=n;i++) add(0,i,0); //建立超级源点 //dist[i]<=dist[0]+0
	if(!spfa()) printf("NO");
	else
	{
		for(int i=1;i<=n;i++)
		{
		    	cout<<dist[i]<<" ";
		}
	}
	return 0;
}

最长路

#include<bits/stdc++.h>
using namespace std;
const int N=5010,M=10010;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
int cnt[N],q[N];
bool st[N];
int dist[N];
void add(int a,int b,int c)
{
	e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
bool spfa() //判断是否存在负环
{
	queue<int> q;
	memset(dist,-0x3f,sizeof dist);
	dist[0]=0;
	q.push(0);
	st[0]=1;
	while(q.size())
	{
		int t=q.front();
		q.pop();
		st[t]=0;
		for(int i=h[t];i!=-1;i=ne[i])
		{
			int j=e[i];
			if(dist[j]<dist[t]+w[i]) //距离可以变大
			{
				dist[j]=dist[t]+w[i];
				cnt[j]=cnt[t]+1;
				if(cnt[j]>=n+1) return false;
				if(!st[j])
				{
					q.push(j);
					st[j]=1;
				}
			}
		}
	}
	return true;
}
int main()
{
	scanf("%d%d",&n,&m);
	memset(h,-1,sizeof h);
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		add(a,b,-c); //dist[b]>=dist[a]+c
	}
	for(int i=1;i<=n;i++) add(0,i,0); //建立超级源点 //dist[i]>=dist[0]+0;
	if(!spfa()) printf("NO");
	else
	{
		for(int i=1;i<=n;i++)
		{
		    	cout<<dist[i]<<" ";
		}
	}
	return 0;
}