差分约束是一群不等关系然后求可行解或者最小值最大值的情况
1.求最大值,用最短路,也就是符号要 (a)>=(b)+c add(b,a,c)
2.求最小值,用最长路,也就是符号要 (a)<=(b)+c add(b,a,c)
目录
信息学奥赛一本通(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
- 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[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<
- }
- 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
- 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[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
- 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(aswap(a,b);
- add(b,a,c);
- }
- while(m2--)//条件2
- {
- int a,b,c;
- cin>>a>>b>>c;
- if(aswap(a,b);
- add(a,b,-c);
- }
- if(spfa())
- {
- if(dist[n]==0x3f3f3f3f) puts("-2");//假如走不到
- else cout<
- }
- else puts("-1");//假如有矛盾
- return 0;
- }
4.雇佣收银员(最长路)
- #include
- 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[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
- {
- int x;
- cin>>x;
- num[x+1]++;//把0空出来当虚拟原点
- }
- bool f=false;
- for(int i=0;i<=1000;i++)//枚举s24可能的情况
- if(spfa(i))
- {
- cout<
- f=true;
- break;
- }
- if(!f) puts("No Solution");
- }
- return 0;
- }
-
相关阅读:
【PostgreSQL】主键添加自增
【Kubernetes | Pod 系列】Pod 的基本管理(3)——对 Pod 的删除与修改
【Linux】Linux常用操作命令
django 开启CSRFtoken校验,以及postman实现问题
数据结构 | (三) Stack
AI办公自动化:批量根据Excel表格内容制作Word文档
HCIP之BGP的路由聚合
PPT素材、PPT模板免费下载
08_一句话让你人间清醒
Java版本spring cloud + spring boot企业电子招投标系统源代码
-
原文地址:https://blog.csdn.net/m0_63729880/article/details/126268525