差分约束
差分约束 是一种特殊的 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;
}
