差分约束

· · 算法·理论

1.差分约束

我们现在有多个不等式，通过这多个不等式，我们可以求出一些未知数的差的最大值或最小值。

一个式子要么是不等式要么是等式，对于一个含三个未知数的式子一定可以表示为 x_a - x_b \le x_c 的形式。

如果是一个等式，那则是 x_a - x_b = x_c 可以表现为 x_a - x_b \le x_c 和 x_a - x_b \ge x_c 两个式子。第二个式子可以在等式两边同时乘上 -1 ，则式子变为 x_b - x_a \le -x_c 的样子。

如果是一个不等式则有两种情况

在如图式子中 \begin{cases} x_{c_1}-x_{c_2}\le y_1 \\x_{c_2}-x_{c_3} \le y_2 \\ \cdots\\ x_{c_{m-1}} - x_{c_m}\le y_m\end{cases}

我们可以得到 x_{c_m} - x_1 \le y_1 + y_2 + y_3 + \cdots + y_m

我们通过与这个式子类似的推算即可得出其中一些未知数两两相减得出的最大值（或最小值）。

如果我们给出 k 个不等式，包含 n 个未知数，那么，该如何求出这个不等式组的一组解。

首先我们可以将不同的不等式化作同一种形式的不等式，我们已经说明过，每个节点我们均可以通过以上的形式得出 x_j - x_i 的解集。

我们可以一眼看出应该用最短路（SPFA），去每组解集中的最小值，但是我们该怎么确定源点呢，它会有多组相连的式子，我们该怎么得出每一组的最短路呢。

我们知道我们的每组节点可能不是联通的，即我们的图是非连通图。在此时我们只需要加入一个虚拟节点，领这个点与所有点相连，那么我们就得到了一个连通图。

那我们该如何设置虚拟节点与其他节点的边的权值呢？其实不难得到虚拟节点的边的边权就是图的初始值。所以可以得出边权的值其实不影响结果。

在进行了一次最短路后我们可以得出了各个点的解，只要输出最短值即可得出结果

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,dis[5005],a,b,c,cmp[5005];
struct xian{
    int v,c;
};
bool vis[5005];
vector<xian> di[5005];
queue<int> q;
bool SPFA(int s) {
    q.push(s);
    vis[s]=1;
    dis[s]=0;
    //cmp[s]=1;
    while(q.size()){
        a=q.front();
        q.pop();
        vis[a]=0;
        for(int i=0; i<di[a].size(); i++)
            if(di[a][i].c+dis[a]<dis[di[a][i].v]){
                dis[di[a][i].v]=di[a][i].c+dis[a];
                cmp[di[a][i].v]++;
                if(cmp[di[a][i].v]>=n)
                    return 1;
                if(!vis[di[a][i].v]){
                    q.push(di[a][i].v);
                    vis[di[a][i].v]=1;
                }
            }
    }
    return 0;
}
signed main(){
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        dis[i]=INT_MAX;
    for(int i=1; i<=m; i++){
        cin>>a>>b>>c;
        di[b].push_back(xian{a,c});
    }
    for(int i=1; i<=n; i++)
        di[0].push_back(xian{i,114514});
    if(SPFA(0))
        cout<<"NO";
    else
        for(int i=1; i<=n; i++)
            cout<<dis[i]<<" ";

    return 0;
}