原题链接
题目描述：小K是个特么喜欢玩MC的孩纸。。。 小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一样。1<=n,m,a,b,c<=10000
输出格式：如果存在某种情况与小K的记忆吻合，输出”Yes”，否则输出”No”。
输入样例： 3 3 3 1 2 1 1 3 1 2 2 3 2
输出样例： Yes
解析：又是一道差分约束的题。。。 对于\(a-b≥c\)，连一条w[b,a]=c的边。 对于\(a-b≤c\)，连一条w[a,b]=-c的边。 对于\(a=b\)，连两条w[a,b]=0,w[b,a]=0的边。 最后跑一遍最长路即可。 注意要用dfs代替spfa，不然会超时。
#include<cstdio> using namespace std; const int maxn = 10005; const int maxm = 30005; int n, m, vis[maxn], dis[maxn]; int nxt[maxm], hed[maxm], to[maxm], val[maxm], cnt; int read(void) { char c; while (c = getchar(), c < '0' || c >'9'); int x = c - '0'; while (c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; return x; } void add(int x, int y, int v) { nxt[++ cnt] = hed[x]; hed[x] = cnt; to[cnt] = y; val[cnt] = v; } int dfs(int u) { vis[u] = 1; for (int i = hed[u]; i ; i = nxt[i]) { int v = to[i]; if (dis[v] < dis[u] + val[i]) { dis[v] = dis[u] + val[i]; if (vis[v] || !dfs(v)) return 0; } } vis[u] = 0; return 1; } int main() { n = read(); m = read(); for (int i = 1; i <= m; ++ i) { int opt = read(); if (opt == 1) { int x = read(), y = read(), v = read(); add(y, x, v); } else if (opt == 2) { int x = read(), y = read(), v = read(); add(x, y, -v); } else { int x = read(), y = read(); add(x, y, 0); add(y, x, 0); } } for (int i = 1; i <= n; ++ i) add(0, i, 0); for (int i = 1; i <= n; ++ i) dis[i] = -2e9; if (dfs(0)) printf("Yes"); else printf("No"); return 0; }转载于:https://www.cnblogs.com/Gaxc/p/10229868.html
相关资源：JAVA上百实例源码以及开源项目