[模板] 差分约束算法

一、题目

点此看题

二、解法

首先把不等式转化成下面的形式： $$x_u\le x_v+y$$那么就相当于$v$连向$u$一个权值为$y$的边，然后去跑最短路。

实现用$\mathtt{s}\mathtt{p}\mathtt{f}\mathtt{a}$，需要判负环（一个点入队大于$n$次就说明有负环）

#include <cstdio> #include <queue> using namespace std; const int M = 5005; int read() { int x=0,f=1;char c; while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;} while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();} return x*f; } int n,m,tot,f[M],dis[M],cnt[M],vis[M]; queue<int> q; struct edge { int v,c,next; }e[2*M]; void fuck() { for(int i=1;i<=n;i++) q.push(i),vis[i]=1; while(!q.empty()) { int u=q.front();q.pop(); cnt[u]++;vis[u]=0; if(cnt[u]>n) {puts("NO");return ;} for(int i=f[u];i;i=e[i].next) { int v=e[i].v,c=e[i].c; if(dis[v]>dis[u]+c) { dis[v]=dis[u]+c; if(!vis[v]) q.push(v),vis[v]=1; } } } for(int i=1;i<=n;i++) printf("%d ",dis[i]); } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(),c=read(); e[++tot]=edge{u,c,f[v]},f[v]=tot; } fuck(); }