题目地址：

https://www.luogu.com.cn/problem/P1993

题目描述：
小K在MC里面建立很多很多的农场，总共$n$个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共$m$个），以下列三种形式描述：
农场$a$比农场$b$至少多种植了$c$个单位的作物；
农场$a$比农场$b$至多多种植了$c$个单位的作物；
农场$a$与农场$b$种植的作物数一样多。
但是，由于小K的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。

输入格式：
第一行包括两个整数$n$和$m$，分别表示农场数目和小K记忆中的信息数目。
接下来$m$行：
如果每行的第一个数是$1$，接下来有三个整数$a,b,c$，表示农场$a$比农场$b$至少多种植了$c$个单位的作物；
如果每行的第一个数是$2$，接下来有三个整数$a,b,c$，表示农场$a$比农场$b$至多多种植了$c$个单位的作物;
如果每行的第一个数是$3$，接下来有两个整数$a,b$，表示农场$a$种植的的数量和$b$一样多。

输出格式：
如果存在某种情况与小 K 的记忆吻合，输出 Yes，否则输出 No。

数据范围：
对于$100\%$的数据，保证$1\le n,m,a,b,c\le 5\times 10^3$。

差分约束问题，可以用最短路或者最长路来解决。考虑有$n+1$个点的最短路问题，点的编号为$0,1,...,n$，$0$是超级源点，以其为源点考虑最短路问题。对于$1$类型的不等式，即有$a-b\ge c$，等价于$b\le a+(-c)$，可以从点$a$到点$b$连一条长度为$-c$的有向边；对于$2$类型的不等式，即有$a-b\le c$，等价于$a\le b+c$，可以从$b$到$a$连一条长度为$c$的有向边；对于$3$类型的不等式，即有$a=b$，可以将$a$和$b$之间互相连一条长度为$0$的有向边。最后从超级源点$0$向其余每个点连一条长度为$0$的有向边，最后解以$0$为源点的最短路问题即可。如果存在负环，则不存在最短路，说明无解，否则说明有解。判断负环的问题可以用SPFA，并且将队列改为栈更适合判断负环。代码如下：

#include <iostream>
#include <cstring>
#include <stack>
using namespace std;const int N = 5e3 + 10, M = N << 1;
int n, m;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], cnt[N];
bool vis[N];void add(int a, int b, int c) {e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}bool spfa() {stack<int> stk;for (int i = 1; i <= n; i++) {stk.push(i);vis[i] = true;}while (stk.size()) {int t = stk.top(); stk.pop();vis[t] = false;for (int i = h[t]; ~i; i = ne[i]) {int v = e[i];if (dist[v] > dist[t] + w[i]) {dist[v] = dist[t] + w[i];cnt[v] = cnt[t] + 1;if (cnt[v] > n - 1) return false;if (!vis[v]) {stk.push(v);vis[v] = true;}}}}return true;
}int main() {memset(h, -1, sizeof h);scanf("%d%d", &n, &m);for (int i = 1; i <= m; i++) {int type, a, b, c;scanf("%d", &type);if (type == 3) {scanf("%d%d", &a, &b);add(a, b, 0), add(b, a, 0);} else {scanf("%d%d%d", &a, &b, &c);if (type == 1) add(a, b, -c);else add(b, a, c);}}if (spfa()) puts("Yes");else puts("No");
}

时间复杂度$O(nm)$，空间$O(n)$。