差分约束

前置芝士#

定义#

{% label 来自OI-Wiki blue %}

差分约束系统 是一种特殊的元一次不等式组，它包含个变量以及个约束条件，每个约束条件是由两个其中的变量做差构成的，形如，其中并且是常数（可以是非负数，也可以是负数）。我们要解决的问题是：求一组解，使得所有的约束条件得到满足，否则判断出无解。

思路#

我们将每个约束条件变形成,然后这个形式很像单源最短路中的。因此，我们可以把每个变量看做图中的一个结点，对于每个约束条件，从结点向结点连一条长度为的有向边。

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

实现#

#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;
}

cpp

前置芝士#

定义#

思路#

实现#

Comments