差分约束是一群不等关系然后求可行解或者最小值最大值的情况
1.求最大值，用最短路，也就是符号要 （a）>=（b）+c add(b,a,c)
2.求最小值，用最长路，也就是符号要 （a）<=（b）+c add(b,a,c)
1.糖果（最长路）
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
x==1 说明a==b 则a>=b且b>=a
x==2 说明b>a 则b>=a+1
x==3 说明a>=b
x==4 说明a>b 则a>=b+1
x==5 说明b>=a
因为保证每个小孩都有一个糖果，则每个小孩>=0+1
#include<bits/stdc++.h> using namespace std; const int N=1e5+10,M=3e5+10; typedef long long ll; int h[N],e[M],ne[M],w[M],idx; ll dist[N]; int cnt[N],q[N]; bool st[N]; int n,k; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool spfa() { memset(dist,-0x3f,sizeof dist); int tt=1; q[0]=0;//用虚拟原点0号点更新其他点的最长路 dist[0]=0; while(tt!=0) { int t=q[--tt];//用栈优化 st[t]=false; for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(dist[j]<dist[t]+w[i])//更新最长距离 { dist[j]=dist[t]+w[i]; cnt[j]=cnt[t]+1; if(cnt[j]>=n+1) return false;//假如更新了n+1次则有负环 if(!st[j]) { q[tt++]=j; st[j]=true; } } } } return true;//反之没负环 } int main() { cin>>n>>k; memset(h,-1,sizeof h); for(int i=1;i<=n;i++) add(0,i,1);//保证每个小朋友都有一个糖果，且0这个虚拟原点可以走所有的边 i>=0+1 while(k--) { int x,a,b; scanf("%d%d%d",&x,&a,&b); if(x==1) add(b,a,0),add(a,b,0);//a>=b+0且b>=a+0 else if(x==2) add(a,b,1);//b>=a+1 else if(x==3) add(b,a,0);//a>=b else if(x==4) add(b,a,1);//a>=b+1 else add(a,b,0);//b>=a } if(spfa())//假如没负环，也就是没有小孩子有矛盾，则输出 { ll res=0; for(int i=1;i<=n;i++) res+=dist[i]; cout<<res<<endl; } else puts("-1"); return 0; }
2.区间（最长路）
条件1：保证i比i-1选的数大于或者等于，则i>=i-1
条件2：由于当前数i有；两种情况选或者不选，则i-(i-1)<=1,则（i-1）>=i-1
条件3：题目输入，则b-(a-1)>=c，则b>=(a-1)+c
#include<bits/stdc++.h> using namespace std; const int N=50010,M=150010; int h[N],e[M],ne[M],w[M],idx; int dist[N]; int q[N]; bool st[N]; int n; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void spfa()//常规spfa { memset(dist,-0x3f,sizeof dist); int hh=0,tt=1; q[0]=0; dist[0]=0; while(hh!=tt) { int t=q[hh++]; if(hh==N) hh=0; st[t]=false; for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(dist[j]<dist[t]+w[i]) { dist[j]=dist[t]+w[i]; if(!st[j]) { q[tt++]=j; if(tt==N) tt=0; st[j]=true; } } } } } int main() { scanf("%d",&n); memset(h,-1,sizeof h); for(int i=1;i<=50001;i++) add(i-1,i,0),add(i,i-1,-1);//条件1和2 while(n--) { int a,b,c; scanf("%d%d%d",&a,&b,&c); if(a>b) swap(a,b); a++,b++; add(a-1,b,c);//条件3 } spfa();//因为一定有解不用判断负环 printf("%d\n",dist[50001]);//输出前50001个的数 return 0; }
3.排队布局（最短路）
信息学奥赛一本通（C++版）在线评测系统 (ssoier.cn)
条件0：两两头牛距离至少为0 则i-(i-1)>=0 对应(i-1)<=i-0
条件1：距离最多为d 则a-b<=d 对应a<=b+d
条件2：距离最少为d 则a-b>=d 对应b<=a-d
#include<bits/stdc++.h> using namespace std; const int N=1010,M=2e4+10; int h[N],e[M],ne[M],w[M],idx; int dist[N]; int q[N],cnt[N]; bool st[N]; int n,m1,m2; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } bool spfa()//常规spfa判断负环 { memset(dist,0x3f,sizeof dist);//求最短路初始化最大值 int hh=0,tt=1; q[0]=1; dist[1]=0; while(hh!=tt) { int t=q[hh++]; if(hh==N) hh=0; st[t]=false; for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(dist[j]>dist[t]+w[i])//求最短路 { dist[j]=dist[t]+w[i]; cnt[j]=cnt[t]+1; if(cnt[j]>n) return false; if(!st[j]) { q[tt++]=j; if(tt==N) tt=0; st[j]=true; } } } } return true; } int main() { cin>>n>>m1>>m2; memset(h,-1,sizeof h); for(int i=1;i<=n;i++) add(i,i-1,0);//条件0 while(m1--)//条件1 { int a,b,c; cin>>a>>b>>c; if(a<b) swap(a,b); add(b,a,c); } while(m2--)//条件2 { int a,b,c; cin>>a>>b>>c; if(a<b) swap(a,b); add(a,b,-c); } if(spfa()) { if(dist[n]==0x3f3f3f3f) puts("-2");//假如走不到 else cout<<dist[n]<<endl; } else puts("-1");//假如有矛盾 return 0; }
4.雇佣收银员（最长路）
#include <bits/stdc++.h> using namespace std; const int N=30,M=100; int dist[N]; int q[N],cnt[N]; bool st[N]; int r[N],num[N]; int n; int h[N],e[M],ne[M],w[M],idx; void add(int a,int b,int c) { e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++; } void built(int s24)//s24是常数也就是枚举的答案 { memset(h,-1,sizeof h); idx=0; for(int i=1;i<=24;i++) { add(i-1,i,0);//si-s(i-1)>=0 add(i,i-1,-num[i]);//si-s(i-1)<=num[i] } for(int i=8;i<=24;i++) add(i-8,i,r[i]);//当大于等于8时，si-s(i-8)>=ri for(int i=1;i<=7;i++) add(i+16,i,-s24+r[i]);//当小于8时，si+s(24)-s(i+16)>=ri add(0,24,s24),add(24,0,-s24);//要保证24这个点是个常数则s(24)<=s(0)+s24,s(24)>=s(0)+s24 } bool spfa(int s24)//s24是常数也就是枚举的答案 { built(s24);//建图 //跑一遍spfa memset(dist,-0x3f,sizeof dist); memset(st,0,sizeof st); memset(cnt,0,sizeof cnt); int hh=0,tt=1; q[0]=0; dist[0]=0; st[0]=true; while(hh!=tt) { int t=q[hh++]; if(hh==N) hh=0; st[t]=false; for(int i=h[t];~i;i=ne[i]) { int j=e[i]; if(dist[j]<dist[t]+w[i]) { dist[j]=dist[t]+w[i]; cnt[j]=cnt[t]+1; if(cnt[j]>=25) return false; if(!st[j]) { q[tt++]=j; if(tt==N) tt=0; st[j]=true; } } } } return true; } int main() { int T; cin>>T; while(T--) { memset(num,0,sizeof num); for(int i=1;i<=24;i++) cin>>r[i]; cin>>n; for(int i=0;i<n;i++) { int x; cin>>x; num[x+1]++;//把0空出来当虚拟原点 } bool f=false; for(int i=0;i<=1000;i++)//枚举s24可能的情况 if(spfa(i)) { cout<<i<<endl; f=true; break; } if(!f) puts("No Solution"); } return 0; }
