题目大意：要求给 $n$ 个人分配糖果，记第 $i$ 个人分配到的糖果数为 $S_i$，要求 $S_i > 0$。另外有 $k$ 个限制，每个限制形如 $X A B(X \in [1,5])$，分别表示：

$X=1,S_A = S_B$

$X=2,S_A < S_B$

$X=3,S_A \geq S_B$

$X=4,S_A > S_B$

$X=5,S_A \leq S_B$

求至少需要多少糖果？

题解：差分约束。

对于差分不等式，$a − b \leq c$，建一条 $b$ 到 $a$ 的权为 $c$ 的边，求的是最短路，得到的是最大值，负环表示无解。

对于差分不等式，$a − b \geq c$，建一条 $b$ 到 $a$ 的权为 $c$ 的边，求的是最长路，得到的是最小值，正环表示无解。

因为求的是最小值，将不等式转化为 $a − b \geq c$ 的形式求最长路即可。注意判自环。

卡点：1.最开始从$0$向各个点连一条权值为$1$的边来跑，$TLE+WA$，改成每个点跑一遍就$AC$了

 

C++ Code：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define maxn 100010using namespace std;const long long inf = 9223372036854775807;int n, k, x, a, b;int head[maxn], cnt;struct Edge {	int to, nxt, w;} e[maxn << 1];void add(int a, int b, int c) {	e[++cnt] = (Edge) {b, head[a], c}; head[a] = cnt;}long long d[maxn];int num[maxn];bool vis[maxn];queue 
         
           q;void spfa(int rt) {	q.push(rt);	while (!q.empty()) {		int u = q.front(); q.pop();		vis[u] = false;		for (int i = head[u]; i; i = e[i].nxt) {			int v = e[i].to;			if (d[v] < d[u] + e[i].w) {				d[v] = d[u] + e[i].w;				num[v]++;				if (num[v] >= n) {					puts("-1");					exit(0);				}				if (!vis[v]) {					vis[v] = true;					q.push(v);				}			}		}	}}int main() {	scanf("%d%d", &n, &k);	for (int i = 0; i < k; i++) {		scanf("%d%d%d", &x, &a, &b);		switch (x) {			case 1: {				add(a, b, 0);				add(b, a, 0);				break;			}			case 2: {				if (a == b) {					puts("-1");					return 0;				}				add(a, b, 1);				break;			}			case 3: {				add(b, a, 0);				break;			}			case 4: {				if (a == b) {					puts("-1");					return 0;				}				add(b, a, 1);				break;			}			default: add(a, b, 0);		}	}	for (int i = 1; i <= n; i++) d[i] = 1;	for (int i = 1; i <= n; i++) {		spfa(i);	}	long long ans = 0;	for (int i = 1; i <= n; i++) ans += d[i];	printf("%lld\n", ans);	return 0;}