背景
小K是个特么喜欢玩MC的孩纸。。。
描述
小K在MC里面建立很多很多的农场，总共n个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得
一些含糊的信息（共m个），以下列三种形式描述：农场a比农场b至少多种植了c个单位的作物，农场a比农场b至多
多种植了c个单位的作物，农场a与农场b种植的作物数一样多。但是，由于小K的记忆有些偏差，所以他想要知道存
不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。
如果存在某种情况与小K的记忆吻合，输出”Yes”，否则输出”No”
Yes
看题意显然是差分约束系统，我们对1这种操作连边 y x z 代表y 比 x 少 z 对2这种连边x y -z 代表x比y少-z （就是多z） 对第三种连 x y 0 和 y x 0.然后跑一遍最长路判环即可
代码如下：
#include <cstdio> #include <algorithm> #include <iostream> #include <deque> #include <cstdlib> using namespace std; const int N = 23123; int head[N], to[N], nxt[N], val[N], _; void add(int x, int y, int z) { to[++_] = y; nxt [_] = head[x]; head[x] = _; val [_] = z; } int vis[N], tot[N], f[N], viss[N]; deque<int> q; int n, m; void spfa(int s) { viss[s]=0; q.push_back(s); while(!q.empty()) { int u = q.front(); q.pop_front(); vis[u] = 0; viss[u] = 1; tot[u]++; if(tot[u]>n) { puts("No"); exit(0); } for(int i=head[u];i;i=nxt[i]) { if(f[to[i]]<f[u]+val[i]) { f[to[i]]=f[u]+val[i]; if(!vis[to[i]]) { if(f[to[i]]>f[q.front()]) q.push_front(to[i]); else q.push_back(to[i]); vis[to[i]]=1; } } } } } int main() { scanf("%d%d", &n, &m); for(int i=1;i<=m;i++) { int opt; scanf("%d", &opt); if(opt==1) { int x, y, z; scanf("%d%d%d", &x, &y, &z); add(y, x, z); } else if(opt==2) { int x, y, z; scanf("%d%d%d", &x, &y, &z); add(x, y, -z); } else { int x, y; scanf("%d%d", &x, &y); add(x, y, 0); add(y, x, 0); } } for(int i=1;i<=n;i++) if(!viss[i])spfa(i); //for(int i=1;i<=n;i++) printf("%d\n", f[i]); puts("Yes"); }
原文：https://www.cnblogs.com/Tobichi/p/9230733.html
