差分约束
差分约束 是一种特殊的 n 元一次不等式组，m 个约束条件，可以组成形如下的格式：
{ x 1 − x 1 ′ ≤ y 1 x 2 − x 2 ′ ≤ y 2 ⋯ x m − x m ′ ≤ y m \begin{cases} x_1-x_1^{'} \le y_1 \\ x_2-x_2^{'} \le y_2 \\ \cdots \\ x_m-x_m^{'} \le y_m \end{cases} ⎩ ⎨ ⎧x1−x1′≤y1x2−x2′≤y2⋯xm−xm′≤ym
我们的任务是需要求出一组解， x 1 = a 1 , x 2 = a 2 , ⋯ , x n = a n x_1=a_1,x_2=a_2,\cdots,x_n=a_n x1=a1,x2=a2,⋯,xn=an
使得不等式组成立，否则为无解
注意到，每个式子都可以变形为 x i ≤ x i ′ + y i x_i\le x_i^{'}+y_i xi≤xi′+yi
那么就不难想到，图论中的 三角不等式 ，即为松弛操作
回忆——
if(dis[edge[i].to]>dis[t]+edge[i].w)dis[edge[i].to]=dis[t]+edge[i].w;
虽说它这里是 >，不过也没有关系，不用考虑
既然知道了，那我们就按照图论的方法来解：
设dis[0]=0 ,并且向着每一个节点连接一条权值为0的边，运用单源最短路，判断 负权环 ，若有负权环则为无解，否则依次输出 dis[i]
提到负权环，就不得不提判断负权环的大佬算法——SPFA！！！
对于那些不废 SPFA 的同学们，可以翻到我之前的博客区康康~~
好啦，看模板题——
luoguP5960 [模板]差分约束
AC Code:
#include<bits/stdc++.h>
using namespace std;
int n,m,cntedge;
const int MAXM=5e3+5,inf=65;
struct EDGE{int to,w,pre;
}edge[MAXM<<1];
int head[MAXM];
void add(int from,int to,int w)
{edge[++cntedge].to=to;edge[cntedge].w=w;edge[cntedge].pre=head[from];head[from]=cntedge;return;
}
bool vis[MAXM];
int u,v,w,t;
int dis[MAXM],cnt[MAXM];
queue<int> q;
bool spfa()
{q.push(0);cnt[0]++;vis[0]=true;while(!q.empty()){t=q.front();q.pop();vis[t]=false;for(int i=head[t];i;i=edge[i].pre){if(dis[edge[i].to]>dis[t]+edge[i].w){dis[edge[i].to]=dis[t]+edge[i].w;if(vis[edge[i].to]) continue;q.push(edge[i].to);vis[edge[i].to]=true;if(++cnt[edge[i].to]>=n+1)return false;}}}return true;
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) add(0,i,0);for(int i=1;i<=m;i++){scanf("%d%d%d",&u,&v,&w);add(v,u,w);}memset(dis,inf,sizeof(dis));dis[0]=0;if(!spfa())printf("NO\n");else{for(int i=1;i<=n;i++)printf("%d ",dis[i]);printf("\n");} return 0;
}
