题目地址：洛谷：【P1993】小K的农场 – 洛谷

题目描述

小K在MC里面建立很多很多的农场，总共n个，以至于他自己都忘记了每个农场中种植作物的具体数量了，他只记得一些含糊的信息（共m个），以下列三种形式描述：

• 农场a比农场b至少多种植了c个单位的作物，
• 农场a比农场b至多多种植了c个单位的作物，
• 农场a与农场b种植的作物数一样多。

但是，由于小K的记忆有些偏差，所以他想要知道存不存在一种情况，使得农场的种植作物数量与他记忆中的所有信息吻合。

输入输出格式

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

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

输入输出样例

输入样例#1：

3 3
3 1 2
1 1 3 1
2 2 3 2

输出样例#1：

Yes

说明

对于 100% 的数据保证：1 ≤ n，m，a，b，c ≤ 10000。

题解

一个差分约束的裸题。
我们考虑一组条件：
\begin{gathered} f(a) - f(b) \leq p \\ f(b) - f(c) \leq q \end{gathered}
显然有f(a) - f(c) \leq p + q。这个可以用图上的边表示出来，我们从a向b连边权p的边，b向c连边权q的边，则产生了a到c的路径，路径权值和为p+q，就能表示上面的不等式合并。
我们考虑如果a到c有多条路径，对应的是一组形如f(a) - f(c) \leq k_i的条件，我们肯定只取f(a) - f(c) \leq \min\{k_i\}即可，这在图上就是最短路。
对于本题，条件1是f(a) - f(b) \geq c转化为f(b) - f(a) \leq -c建边，条件2直接建边，条件3为f(a) - f(b) = 0，用f(a) - f(b) \leq 0和f(b) - f(a) \leq 0来表示。
差分约束系统存在可行解的充要条件是图中不存在负环，即满足对于任意点，不存在f(a) - f(a) < 0的情况。我们用DFS式SPFA来判断是否存在负环。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cctype>

#include <vector>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(!isdigit(c)) {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(isdigit(c)) {
        res = (res << 1) + (res << 3) + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MAXN = 10005;

struct Edge {
    int to, w;
};
std::vector<Edge> gra[MAXN];

int n, m;

int dis[MAXN];
bool vis[MAXN], has;

inline void dfs(int u) {
    vis[u] = true;
    for(Edge e : gra[u]) {
        int v = e.to;
        if(dis[v] > dis[u] + e.w) {
            if(vis[v]) {
                has = true;
                return;
            }
            dis[v] = dis[u] + e.w;
            dfs(v);
        }
        if(has) return;
    }
    vis[u] = false;
}

int op, a, b, c;

int main() {
    n = readint(); m = readint();
    while(m--) {
        op = readint(); a = readint(); b = readint();
        if(op == 1) {
            c = readint();
            gra[b].push_back(Edge {a, -c});
        } else if(op == 2) {
            c = readint();
            gra[a].push_back(Edge {b, c});
        } else {
            gra[a].push_back(Edge {b, 0});
            gra[b].push_back(Edge {a, 0});
        }
    }
    for(int i = 1; i <= n; i++) {
        dfs(i);
        if(has) break;
    }
    if(has) puts("No"); else puts("Yes");
    return 0;
}