【题解】（求赞）

差分约束的经典题目

别以为拿MC做题干我就看不懂

差分约束简介：(前置知识SPFA)
当我们得到一个不等式组，
形似：

A - 1 >= B

我们就会发现通过移项可以得到:

A >= B + 1

这时就会发现这和我们在松弛dist数组时用到的：

dist[v] >= dist[u] + w

极为相似。因此，可以利用这一特点，构造一个图。跑最短（或最长路）来对此不等式组进行求最值、求是否存在根等操作。

具体代码：

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;

const int N = 5e3 + 5;
int a[N],dist[N],vis[N],vvis[N];
vector<pii> g[N];

int main(){
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= m;i ++){
        int key,a,b,c;
        cin >> key;
        if(key == 1){
            cin >> a >> b >> c;
            g[a].push_back({b,-c});
            //这里代表b <= a - c（我跑最短路，如果跑最长路的话要转换成>=）
        } else if(key == 2){
            cin >> a >> b >> c;
            g[b].push_back({a,c});
        } else {
            cin >> a >> b;
            g[a].push_back({b,0});
            g[b].push_back({a,0});//互相建零边代表相等（这个好理解）
        }
    }
    for(int i = 1;i <= n;i ++){
        g[0].push_back({i,0});
        //建一个超级原点来处理不完全连通的图 
    }
    memset(dist,0x3c,sizeof dist);
    dist[0] = 0;
    queue<int> q;
    q.push(0);

    while(q.size()){//SPFA
        int ip = q.front();
        q.pop();
        vis[ip] = 0;
        for(int i = 0;i < g[ip].size();i ++){
            int v = g[ip][i].first,w = g[ip][i].second;
            if(dist[v] > dist[ip] + w){
            //我这是最短路写法，要跑最长路也可以。只不过要改前面建边的部分
                dist[v] = dist[ip] + w;
                if(!vis[v]){
                    vvis[ip] ++;
                    if(vvis[ip] > n){//判有负环代表不等式组无根
                        cout << "No";
                        return 0;
                    }
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    cout << "Yes";
    return 0;
}