差分约束

问题类型描述

• 给定 n n n个变量和 m m m个约束条件，如 x i − x j ≤ c k x_i-x_j\leq c_k xi​−xj​≤ck​，让你求一组解，是的所有的约束条件均被满足。

模型转换

• 变形一下： x i ≤ x j + c k x_i\leq x_j + c_k xi​≤xj​+ck​

  • 容易发现，与最短路中的 d i s [ v ] ≤ d i s [ u ] + w dis[v]\leq dis[u]+w dis[v]≤dis[u]+w非常相似

• 如何理解？

  • 如果 u u u与 v v v之间有一条连边，那么 d i v [ v ] div[v] div[v]的值，要嘛 = = d i s [ u ] + w ==dis[u]+w ==dis[u]+w,要嘛 < d i s [ u ] + w <dis[u]+w <dis[u]+w

    因为有那条连边在哪，所以可以被松弛操作，只要是 d i s [ v ] > d i s [ u ] + w dis[v]>dis[u]+w dis[v]>dis[u]+w，那么这个情况就可以被松弛

• 然后我们就将不等式问题转换成为一个最短路径问题

思维递进

• 接下来我们的 x [ 1 − n ] x[1-n] x[1−n]就等价于 d i s [ 1 − n ] dis[1-n] dis[1−n]了，然后我们要求解的就是 d i s [ 1 − n ] dis[1-n] dis[1−n]了，即求解最短路

• 只要存在有向边边，就满足那个不等式的条件，跑最短路求出所有的最短距离 d i s [   ] dis[~] dis[ ]即可

  源点如何选取？

• 因为是有向图，我们要遍历到所有节点，所以需要建立一个超级源点0号

  • 我们选定是一种“关系”，所以整体偏移一个数值，答案依旧是正确的
  • 所有节点到 0 0 0的距离为一个定值 d d d，一般的博客里面都是设置为 0 0 0，当然你改为 114514 114514 114514也是没有差别的
  • 毕竟只是一个偏移量

不等式组无解

• 什么情况下，上面的多项式组无解？

• 在我们转换的模型中，如果一个点的最短距离 d i s [ i ] dis[i] dis[i]不存在，即非负无穷大——>存在负环

  在原来的方程组里面，就是几个变量相互约束

• 所以就是利用SPFA判断负环的办法即可，即存在num[i]>n

为什么不能用Dijkstra

• Dijkstra不能处理负数边权，已经确立 d i s [ ] dis[] dis[]的点，若有负数边权，可能会被后续进来的点给更新掉。

拓展

• 题目给的形式为 x i − x j ≤ c k x_i-x_j\le c_k xi​−xj​≤ck​

• 若为 x i − x j ≥ c k x_i-x_j\ge c_k xi​−xj​≥ck​

  • 则将两边同时乘以负号，有 x j − x i ≤ c k x_j-x_i\le c_k xj​−xi​≤ck​

• 若为 x i − x j = c k x_i-x_j=c_k xi​−xj​=ck​，即上面二者的统一

  • $x_i-x_j\le c_k 且 且 且 x_j-x_i\leq c_k$，建立双向边即可

代码实现

#include <bits/stdc++.h>
#include <bits/extc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;

#define debug(x) cerr << #x << ": " << x << '\n';
#define bd cerr << "----------------------" << el;
#define el '\n'
#define cl putchar('\n');
#define pb push_back
#define eb emplace_back
#define x first
#define y second
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define lop(i, a, b) for (int i = (a); i < (b); i++)
#define dwn(i, a, b) for (int i = (a); i >= (b); i--)
#define ceil(a, b) (a + (b - 1)) / b
#define ms(a, x) memset(a, x, sizeof(a))
#define INF 0x3f3f3f3f
#define db double
#define all(x) x.begin(),x.end()
#define cmax(a, b) a = max(a, b)
#define cmin(a, b) a = min(a, b)
#define reps(i, x) for (int i = 0; i < x.size(); i++)

typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
typedef pair<db, db> PDD;
typedef vector<int> vci;

template <typename T>
inline void read(T &x)
{
    x = 0;
    T f = 1;
    char c = getchar();
    while (!isdigit(c))
    {
        if(c == '-')
            f = -1;
        c = getchar();
    }
    while (isdigit(c))
    {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    x *= f;
}

const int N = 1e5 + 10, M = 2e6 + 10, B = 66, md = 1e9 + 7;
const double PI = acos(-1), eps = 1e-8;

int T, n, m;

vector<PII> g[N];
int vis[N], dis[N];
bool inq[N];


int main()
{
    read(n), read(m);
    queue<int> q;
    rep(i, 1, m)
    {   int u, v, w;
        read(v), read(u), read(w);
        g[u].pb({v, w});
    }
    rep(i, 1, n)
    {
        g[0].pb({i, 0}); //建立0到所有点的边
        //这个0只是一个偏移量，你改为任意值都可以
    }

    memset(dis, 0x3f, sizeof dis);
    dis[0] = 0;
    q.push(0);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        vis[u] ++ ;
        inq[u] = false;
        if(vis[u] > n + 1)
        {
            cout << "NO";
            exit(0);
        }
        #define v g[u][i].first
        #define w g[u][i].second
        reps(i, g[u])
        {
            if (dis[v] > dis[u] + w)
            {
                dis[v] = dis[u] + w;
                if(!inq[v])
                {
                    inq[v] = true;
                    q.push(v);
                }
            }
        }
        #undef v
        #undef w
    }
    rep(i, 1, n)
    {
        cout << dis[i];
        if( i < n) cout << ' ';
    }
}