题解 P5960 【【模板】差分约束算法】

Push_Y · 2020-08-09 20:52:03 · 题解

建议先做P3385 【模板】负环】，安利一下我那题的题解

2020.8.14更新，将 'spfa' 等错误改为 spfs 。

差分约束

将给出的不等式条件移项，得到了x_{c}≤x_{c'}+y，可以看成最短路中更新每个节点 dis 的d[v]≤d[u]+w[u][v]，然后就是写最短路啦。

如何判断负环？

用 spfa 跑最短路的时候，每次判断队首点的入队次数是否已经达到 n-1 。若有一次满足该条件，则有负环。

一些注意点

• 把每个节点与 i 相连的时候倒着 for ，因为数据是卡 spfa 的。
• 结构体存两倍 N 的大小
• 更多精彩尽在下方代码中

附带详细注释的代码

#include <bits/stdc++.h>
using namespace std;

inline int gin(){//快读
    char c=getchar();
    int s=0,f=1;
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        s=(s<<3)+(s<<1)+(c^48);
        c=getchar();
    }
    return s*f;
}

const int N=5e3+5;
int n,m,cnt[N],d[N],tot=0,head[N];
//cnt记录入队次数
bool h[N],t;
//t记录是否为负环
queue<int> q;

struct edge{//用结构体存储链接表
    int dis,ne,to;
}e[N<<1];

inline void add(int u,int v,int w){//连边
    e[++tot].dis=w;
    e[tot].to=v;
    e[tot].ne=head[u];
    head[u]=tot;
}

inline void spfa(){//最短路
    memset(d,63,sizeof d);//初始化
    h[0]=1,t=0,d[0]=0;
    q.push(0);
    while(q.size()){
        int u=q.front();q.pop();h[u]=0;
        if(cnt[u]==n-1){t=1;return;}//如果已经入队了n-1次就出现负环了
        cnt[u]++;
        for(int i=head[u];i;i=e[i].ne){
            int v=e[i].to,w=e[i].dis;
            if(d[v]>d[u]+w){
                d[v]=d[u]+w;
                if(!h[v])h[v]=1,q.push(v);
            }
        }
    } 
}

int main(){
    n=gin(),m=gin();
    for(int i=1;i<=m;i++){
        int u=gin(),v=gin(),w=gin();
        add(v,u,w);
    }
    for(int i=n;i>=1;i--)add(0,i,0);//之前正序被卡，感谢题解区大佬解释
    spfa();
    if(t){printf("NO");return 0;}
    for(int i=1;i<=n;i++)printf("%d ",d[i]);
    return 0;
}