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

***

题面：

> *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$$ 和最短路的三角不等式$$dist\[y]<=dist\[x]+z$$ 相似，所以可以把每个变量都看作一个点，每个约束条件相当于从节点$$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";
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.mcyou.cc/suan-fa-xiang-guan/suan-fa/ji-xun-zheng-li-cha-fen-yue-shu-mu-ban-ti.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.