2023.5.6 写的太烂了重新写
差分约束系统
定义
差分约束系统是一种特殊的 (n) 元一次不等式组，它包含 (n) 个变量 (x_{1},x_{2},…,x_{n}) 以及 (m) 个约束条件，每一个约束条件都是两个其中的变量做差构成的，形如 (x_{i}-x_{j}le c_{k})，其中 (1le i,jle n,ine j,1le kle m) 并且 (c_{k}) 是常数（可以为正数或非正数）。
——- OI Wiki
通俗一点讲，这类问题都是给定 (n) 个变量，(m) 个限制，类似于：
op_{1}:x_{1}-x_{2}=c_{1}\
op_{2}:x_{4}-x_{n}=c_{2}\
……\
op_{m}:x_{n}-x_{3}=c_{m}
end{matrix}right. ]
有了这些条件，一般的题目会让你求出一组合法的解，也就是求这 (n) 个变量的合法的值。
过程
我们可以建一个超级源点，然后向每一个点连一条边权为 (0) 的边，然后跑单源最短路；而上面的 (m) 个限制都可以变形为 (x_{i}le x_{j}+c_{k})，这个东西很容易想到我们在跑最短路的时候的松弛操作里的 (dis[v]le dis[u]+w)，因此我们就可以把每一个变量看作是一个图中的点，对于每一个条件 (x_{i}-x_{j}le c_{k})，从 (j) 向 (i) 连一条边权为 (c_{k}) 的有向边。
我们在求解的时候一般用 SPFA 来跑，虽然他最坏的时间复杂度是 (O(nm)) 的，但是我们的差分约束里面要是有负环的话，就说明是无解，再加上有负边权，SPFA 这个已死的算法成了最好的方法，更何况他在一些随机的图中跑的飞快。
最后一个问题，最后转化的式子是 (x_{i}le x_{j}+c_{k})，为什么跑最短路？
但是我觉得，当你建图的时候使用的是 (x_{i}-x_{j}le c_{k}) 形式的方程组建图时，即 (j) 向 (i) 连一条权值为 (c_{k}) 的边，应该选择跑最短路。
如果使用的是 (x_{i}-s_{j}ge c_{k}) 形式的方程组来建图时，应该选择跑最长路。
P5960 【模板】差分约束算法
code:
#include
#define INF 0x3f3f3f3f
#define N 50100
using namespace std;
int n,m,cnt,head[N];
queueq;
struct SB{int w,v,next;}e[Ndis[u]+w)
{
dis[v]=dis[u]+w;
q.push(v);
vis[v]=1;
tot[v]++;
if(tot[v]==n+1)
return 0;
}
}
}
return 1;
}
int main()
{
cin>>n>>m;
for(int i=1;i>x>>y>>z;
add(y,x,z);
}
if(!SPFA())
cout服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
机房租用，北京机房租用，IDC机房托管， http://www.e1idc.net
