最短路三角形不等式:Xi<=Xj+w（根据最短路的定义，要是不满足的话就不是最短路了）
给出若干个形如Xi-Xj<=w的约束条件，考虑求一组合法的解。
把问题转化成求最短路，对于Xi-Xj<=w，我们从j向i连一条边权为w的边
如果有负环的话即无解。
...?
但差分约束难搞一点的话还要求最大解、最小解，以及其他更多的满足条件。
1.先看看求最大解。
可能有点反直觉，但是：通过最短路径算出来的未知数都能到最大值
粗略证明:假设M1，M2，M3..是一组合法的最大解，根据Bellman-Ford的过程，一开始的路径都初始化为无穷大，然后检查所有三角形不等式，不满足最短路三角形不等式则更新。最后求出来的dis数组就是到每个点的最短路长度。
那我们初始化为无穷大时，求出来的是D1,D2,D3...初始化为M1,M2,M3时，求出来的就是M1，M2，M3..(刚才已经假设这组M是合法的解，不再更新)。那么D1,D2,D3..==M1,M2,M3..因为同一个算法，同一个过程，总不能因为初始值设置大了，答案反而小了吧？
所以求最大解时跑最短路，且不等式的形式都要形如Xi-Xj<=w，然后从j向i连边权为w的边。
一些常见的最短路变形：
Xi>Xj , Xi>=Xj+1, Xj-Xi<=-1
Xi-Xj>=k, Xj-Xi<=-k
Xi==Xj，拆成Xi>=Xj,Xj>=Xi
Xi-Xj==k,拆成Xi-Xj>=k,Xi-Xj<=k,再对第一个进行变形得Xj-Xi<=-k
更新时的注意事项：
初始化为无穷大，用最短路三角形不等式更新:
if(dis[v]>dis[u]+e[i].w) dis[v]=dis[u]+e[i].w;
2.同理的，求解最小值时等价为跑最长路
最长路满足的三角形不等式：Xi-Xj>=w
不等式都要变形成形如Xi-Xj>=w的形式，从j向i连边权为w的边
初始化为无穷小，注意更新时符号也要变化
if(dis[v]<dis[u]+w) dis[v]=dis[u]+w;
3.玄学的优化
你应该知道，关于spfa，它死了的这件事..
今天一道构造题写了差分约束，t25，赛后学长说换成双端队列随机取队头队首，或者把queue改成stack可能会有奇效
测了一下随机化是过了，栈没过。不是很明白原理，可能是根据卡spfa的数据出的?
4.此题的代码:
//stack ， T25
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int tot,n,m,l,r,k;
int a[maxn];
struct lys{
int from,to,nex;
ll val;
}e[int(1e6)];
int head[int(1e6)];
void add(int from,int to,ll val){
tot++;e[tot].from=from;e[tot].to=to;
e[tot].val=val;e[tot].nex=head[from];head[from]=tot;
}
int cnt[maxn];
bool vis[maxn];
ll dis[maxn];
stack<int>s;
bool spfa(void)
{
for(int i=1;i<=n;i++) dis[i]=LONG_LONG_MIN;
dis[0]=0;
vis[0]=true;
s.push(0);
while(!s.empty())
{
int u;
u=s.top();s.pop();
vis[u]=false;
for(int i=head[u];i;i=e[i].nex)
{
int v=e[i].to;ll w=e[i].val;
if(dis[v]<dis[u]+w)
{
dis[v]=dis[u]+w;
if(!vis[v])
{
vis[v]=true;
cnt[v]++;
if(cnt[v]>=n+1) return false;
s.push(v);
}
}
}
}
return true;
}
int main()
{
fastio;
cin>>n>>l>>r>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<n;i++){
if(a[i]==a[i+1]){
add(i,i+1,0);
add(i+1,i,0);
}
else if(a[i+1]>a[i]){
// i+1 <= i + k
add(i+1,i,-k);
// i+1 >= i + 1 -> i <= i+1 -1
add(i,i+1,1);
}
else {
add(i+1,i,1);
add(i,i+1,-k);
}
}
for(int i=1;i<=n;i++){
add(0,i,l);
}
if(!spfa())
{
cout<<-1<<endl;
return 0;
}
else {
bool valid=true;
for(int i=1;i<=n;i++){
if(dis[i]>r) valid=false;
}
if(!valid){
cout<<-1;
}
else {
for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
}
}
return 0;
}
加了随机优化的双端队列，accepte
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int tot,n,m,l,r,k;
int a[maxn];
struct lys{
int from,to,nex;
ll val;
}e[int(1e6)];
int head[int(1e6)];
void add(int from,int to,ll val){
tot++;e[tot].from=from;e[tot].to=to;
e[tot].val=val;e[tot].nex=head[from];head[from]=tot;
}
int cnt[maxn];
bool vis[maxn];
ll dis[maxn];
bool spfa(void)
{
for(int i=1;i<=n;i++) dis[i]=LONG_LONG_MIN;
dis[0]=0;
deque<int> q;
q.push_front(0);
vis[0]=true;
while(!q.empty())
{
int u;
if(rand()&1)u=q.front(),q.pop_front();
else u=q.back(),q.pop_back();
vis[u]=false;
for(int i=head[u];i;i=e[i].nex)
{
int v=e[i].to;ll w=e[i].val;
if(dis[v]<dis[u]+w)
{
dis[v]=dis[u]+w;
if(!vis[v])
{
vis[v]=true;
cnt[v]++;
if(cnt[v]>=n+1) return false;
q.push_front(v);
}
}
}
}
return true;
}
int main()
{
fastio;
cin>>n>>l>>r>>k;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<n;i++){
if(a[i]==a[i+1]){
add(i,i+1,0);
add(i+1,i,0);
}
else if(a[i+1]>a[i]){
// i+1 <= i + k
add(i+1,i,-k);
// i+1 >= i + 1 -> i <= i+1 -1
add(i,i+1,1);
}
else {
add(i+1,i,1);
add(i,i+1,-k);
}
}
for(int i=1;i<=n;i++){
add(0,i,l);
}
if(!spfa())
{
cout<<-1<<endl;
return 0;
}
else {
bool valid=true;
for(int i=1;i<=n;i++){
if(dis[i]>r) valid=false;
}
if(!valid){
cout<<-1;
}
else {
for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
}
}
return 0;
}
标签：Xj,Xi,Contest,int,ll,tot,随机化,maxn,优化 From： https://www.cnblogs.com/liyishui2003/p/17107561.html