图论拓展-差分约束

问题

$给出n个不等式,每个不等式都由两个变量的差构成,形如X_i - X_j \leq C_k, 其中C_k为常数$

• 是否存在一组解使不等式成立
• 求一组最小解

分析

$观察不等式X_i - X_j \leq C_k,刚好可以等价便是成一条边$

$在一个有向图中,a 存在一条连向 b 的边,源点到a的最长距离为X_i, 到b的最长距离为X_j,边权为C_k$

$那么X_j至少可以被i更新为X_i + C_k$

$通过不等式建边,因为可能会产生负环(或正环),使不等式无解,所以要用spfa判断负(正)环$

$Code$

#include <bits/stdc++.h>

using namespace std;

const int N = 100010, M = 200010;

int n, k;
int h[N], e[M], w[M], ne[M], idx;
long long d[N];
int q[N], s[N];
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

bool spfa()//判负环模版
{
    int hh = 0, tt = -1;

    for (int i = 1; i <= n; i ++ )
    {
        q[++ tt] = i;
        st[i] = true;
        d[i] = 1;
    }

    while (hh <= tt)
    {
        int t = q[hh ++ ];//出队
        st[t] = false;

        //松弛操作
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (d[j] __ d[t] + w[i])//符号不全
            {
                d[j] = d[t] + w[i];//更改路径
                s[j] = s[t] + 1;//路径经过点的个数
                if (!st[j])st[j] = true, q[++ tt] = j;//入队
                if (s[j] >= n)return true;//产生正负环
            }
        }
    }

    return false;
}

int main()
{
    scanf("%d%d", &n, &k);

    memset(h, -1, sizeof h);
    for (int i = 1; i <= k; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        //建边,最大值最短路,最小值最长路,按题目补全
    }

    spfa();

    return 0;
}