差分约束

前置芝士

👉SPFA单源最短路

定义

来自OI-Wiki blue

差分约束系统 是一种特殊的 $n$ 元一次不等式组，它包含 $n$ 个变量 $x_1,x_2,\dots,x_n$ 以及 $m$ 个约束条件，每个约束条件是由两个其中的变量做差构成的，形如 $x_i-x_j\leq c_k$，其中 $1 \leq i, j \leq n, i \neq j, 1 \leq k \leq m$ 并且 $c_k$ 是常数（可以是非负数，也可以是负数）。我们要解决的问题是：求一组解 $x_1=a_1,x_2=a_2,\dots,x_n=a_n$，使得所有的约束条件得到满足，否则判断出无解。

思路

我们将每个约束条件$x_i-x_j\leq c_k$变形成$x_i\leq x_j+c_k$,然后这个形式很像单源最短路中的 $dist[y]\leq dist[x]+z$ 。因此，我们可以把每个变量 $x_i$ 看做图中的一个结点，对于每个约束条件 $x_i-x_j\leq c_k$，从结点 $\color{red}{j}$ 向结点 $\color{red}{i}$ 连一条长度为 $c_k$ 的有向边。

• 若图不是联通的,我们可以设 $dist[0]=0$ 并向每一个点连一条权重为 $0$ 的边。
• 跑单源最短路若图中存在负环，则给定的差分约束系统无解，否则，$x_i=dist[i]$ 为该差分约束系统的一组解。

实现

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar())if(c=='-')f=-1;
	for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
	return x*f;
}
int n,m;
struct node{
    int to;
    int val;
};
vector<node>ro[100005];
queue<int>Q;
int dis[100005],cnt[100005];
bool vis[100005];
bool spfa(){/* SPFA板子 */
    memset(dis,0x3f3f3f3f,sizeof dis);
    dis[0]=0,vis[0]=true;Q.push(0);
    while(Q.size()){
        int now = Q.front();Q.pop();vis[now] = false;
        for(node to:ro[now]){
            if(dis[to.to]>dis[now]+to.val){
                dis[to.to]=dis[now]+to.val;
                cnt[to.to]=cnt[now]+1;
                if(cnt[to.to]>=n+1/* 这个地方狠狠地注意了！！！一定那个要看清楚负环的边界，不能设小了 */)return false;
                if(!vis[to.to])Q.push(to.to),vis[to.to]=true;
            }
        }
    }
    return true;
}
int main(){
    n=read(),m=read();
    for(int i = 1,u,v,w;i<=m;i++){
        u=read(),v=read(),w=read();
        ro[v].push_back((node){u,w});//加边，注意方向u->v
    }
    for(int i = 1;i<=n;i++){
        ro[0].push_back((node){i,0});//若图不连通，加边，建超级源点
    }
    bool NO_NG_CL = spfa();
    if(!NO_NG_CL)cout<<"NO\n";//判负环（无解）
    else{
        for(int i = 1;i<=n;i++){
            cout<<dis[i]<<" ";
        }
    }
    return 0;
}