差分约束.md

#差分约束
###功能
````
1:求不等式的可行解,
源点满足,从源点出发,一定可以走到所有的边
2:求最大值或最小值
````
###方法
````
形如
Xi<=Xj+Ck
的一堆不等式,可以求出可行解
其中i,j为自变量,c为常数
{
x1<=x2+1
x2<=x3+2
x3<=x1-2
}
对于
Xi<=Xj+Ck
我们类比三角不等式
看做j->i连一条权值为c的边
有dis[i]<=dis[j]+c
因为从j走到i,如果反之则不能走这条边
````
###步骤
````
1:Xi<=Xj+Ck
将不等式格式化,转化为j走到i长度为Ck的边
不一定走到所有点,但一定要能走到所有边,限制的是边
孤立的点也就是没有限制,
2:找到虚拟源点,使得虚拟源点可以到达所有的边
3:从源点求单源最短路

如果存在负环,说明不等式组无解!
如:X1->X2->X1 权值之和小于0
X2<=X1+C1
X1<=X2+C2
放缩X2<=X2+C2+C1
显然矛盾

如果没有负环,则dis[i]就是可行解
做一个对偶Xk>=Xi-Ck
i->连一条-Ck的边
dis[j]>=dis[i]+Ck求最长路

如果是求的最小值,求最长路,
如果求的是最长值,应该求最短路
应该有绝对关系,比如Xi>=0
转化Xi<=c c为常数,这类的不等式
建立超级源点为X0到i长度是0的边
Xi<=C转化为Xi<=X0+C
构成不等式链对应路径,Xi<=Xj+C1<=Xk+C2+C1<=...<=X0+C1+C2...
Xi的最大值为一个所有上界的最小值等价于求0到i路径的最小值