一、差分约束系统
当我们有一组形如\(x_i-x_j\leq c_{i,j}\)的不等式，可以构成一个差分约束系统。
注意到，可将\(x_i-x_j\leq c_{i,j}\)转化为\(x_i\leq x_j+c_{i,j}\)，此时与最短路（单源）的松弛条件\(dist_i\leq dist_j+w(i,j)\)具有高度相似性。由此我们便可结合最短路，去求一组\(x\)为差分约束系统的最小可能值，即\(dist\)。
二、具体实现
对于\(x_i-x_j\leq c_{i,j}\)我们对\(i\)到\(j\)建单向边，边权为\(c_{i,j}\)，由于图可能不连通，建立超级源点\(S\)，将\(S\)向所有节点连一条边权为\(0\)的单向边。这样即可从\(S\)出发，不遗漏的遍历每一个点，这时我们设\(dist_i\)为\(S\)到\(i\)的最短路，即为\(x_i\)的最小可能值。
显然可用SPFA跑单源最短路（显然快于或等于Bellman-Ford，且Dijkstra不能处理含负边的图），但可以发现，若出现负环，则一定无解，否则有解，所以刚好可以使用SPFA判负环，可以用一个\(cnt_v\)记录\(v\)点被遍历的次数，若重复遍历一个点超过节点数，则必出现了负环，差分约束系统无解。
三、扩展
| 式子 | 转换成差分约束 |
|---|---|
| \(x_i-x_j\geq c_{i,j}\) | \(x_j-x_i\leq-c_{i,j}\) |
| \(x_i-x_j=c_{i,j}\) | \(x_i-x_j\leq c_{i,j}\)，\(x_i-x_j\geq c_{i,j}\) |
| \(L_i\leq x_i\leq R_i\) | \(x_i-x_S\leq R_i\)，\(x_S-x_i\leq-L_i\)（其中\(x_S\)即超级源点\(dist_S=0\)） |
四、代码
以防你不会写SPFA，这里提供了SPFA。
int n;
vector<pair<ll,ll> > edge[N];
ll dist[N];
ll cnt[N];//计数
queue<ll> Q;
bool inQ[N];//队中1，队外0
void SPFA(){dist[0]=0;for(int i=1;i<=n;i++)dist[i]=1e18;Q.push(0);while(Q.size()){ll u=Q.front();Q.pop();inQ[u]=0;for(pair<ll,ll> p:edge[u]){ll v=p.first,w=p.second;if(dist[v]>dist[u]+w){dist[v]=dist[u]+w;cnt[v]++;if(cnt[v]>n){cout<<"No";//有负环输出Noreturn;}if(!inQ[v]){Q.push(v);inQ[v]=1;}}}}cout<<"Yes";//结束了都没输出No
}