【集训整理】差分约束 模板题

---

题面：

m 个约束条件，第 j 个约束条件有三个整数_u_,v,w，表示$a\_u-a\_v\le w$

请判断是否至少存在一组 _a_的值满足上述条件。

差分约束系统是一种特殊的n元一次不等式组，包含n个变量及m个约束条件。其中约束条件是由其中两个变量作差构成 ，如$x\_i-x\_j<=c\_k$

这个$x\_i-x\_j<=c\_k$ 和最短路的三角不等式 相似，所以可以把每个变量都看作一个点，每个约束条件相当于从节点$i$向节点i连一条长度为$c\_k$的有向边。判断无解只需要判断图中是否存在负环就可以了。

为了避免不联通的情况，设一个新点n+1，然后让他向每个点都连一条边权为0的边。

所以就把一个不等式组的问题变成了图的问题。对n+1号点跑一遍单源最短路，使用SPFA，判断是否存在负环即可。

SPFA的原版方法：

将起点入队，每次从队列里取一个点，尝试更新（松弛）与这个点连接的所有点的最短路径长度。如果松弛成功，那么将这个点入队（当然，如果队列里已经有了，那就没必要再入队了。用一个数组记录这个数是否已经在队列里了）。

用SPFA求负环的方法：

对于负环，SPFA会对他反复松弛，使最短路变小。所以我们只要记录一下每个节点松弛的次数，如果某个点的松弛次数>n了，那肯定是有负环了。

#include<iostream>
#include<queue>
#include<cstring>
#define N 51000
using namespace std;

int v[N], w[N], nex[N];
int d[N], cnt[N], first[N];
bool vis[N]; int t;
int n,m;

void add(int x, int y, int z){
    t++;
    nex[t] = first[x];
    first[x] = t;
    v[t] = y;
    w[t] = z;
}

bool SPFA(int s){
    int x, y, i, j;
    queue<int>q;
    memset(d, 0x3f, sizeof(d));
    memset(vis, false, sizeof(vis));
    while (!q.empty())  q.pop();
    d[s] = 0;
    cnt[s] = 1;
    q.push(s);
    vis[s] = true;
    while (!q.empty()){
        x = q.front();
        q.pop();
        vis[x] = false;
        for (i = first[x]; i; i = nex[i]){
            y = v[i];
            if (d[y] > d[x] + w[i]){
                d[y] = d[x] + w[i];
                cnt[y] = cnt[x] + 1;
                if (cnt[y] > n)
                    return false;
                if (!vis[y]){
                    q.push(y);
                    vis[y] = true;
                }
            }
        }
    }
    return true;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> b >> a >> c;
        add(a, b, c);
    }
    d[n + 1] = 0;
    for (int i = 1; i <= n; i++) add(n + 1, i,0);
    if (SPFA(n+1))
        cout << "YES";
    else
        cout << "NO";
}