-
2019-05-17 20:52:05
差分约束
1.差分约束系统(system of difference constraints)
如果一个系统由n个变量和m个约束条件组成,形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),则称其为差分约束系统(system of difference constraints)。亦即,差分约束系统是求解关于一组变量的特殊不等式组的方法。
求解差分约束系统,可以转化成图论的单源最短路径(或最长路径)问题。
——百度百科
如下列的不等式组x1-x5≤-1 x2-x5≤1 x3-x1≤5 x4-x1≤4 x4-x3≤-1 x5-x3≤-3 x5-x4≤-3
比如1式 x1-x5≤-1,其中一个未知数x1与x5的差小于等于-1,就相当于设两个未知数x,y差为某一常数,由这些不等式构成的不等式方程组为差分约束系统。
2.例题
小K的农场
关于洛谷一道蓝题。
P1993 小K的农场
但因为在另一篇题解中写过了,所以不多做阐述,解题看好差分约束条件就行了。
小K的农场(差分约束)题解然后是另外两道题
蒜头君的银行卡
Description
虽然蒜头君并没有多少钱,但是蒜头君办了很多张银行卡,共有 n 张,以至于他自己都忘记了每张银行卡里有多少钱了。他只记得一些含糊的信息,这些信息主要以下列三种形式描述:
银行卡 a 比银行卡 b 至少多 c 元。
银行卡 a 比银行卡 b 至多多 c 元。
银行卡 a 和银行卡 c 里的存款一样多。
但是由于蒜头君的记忆有些差,他想知道是否存在一种情况,使得银行卡的存款情况和他记忆中的所有信息吻合。Input
第一行输入两个整数 n 和 m,分别表示银行卡数目和蒜头君记忆中的信息的数目。(1≤n,m≤10000)接下来 m 行:
如果每行第一个数是 1,接下来有三个整数 a,b,c,表示银行卡 a 比银行卡 b 至少多 c元。
如果每行第一个数是 2,接下来有三个整数 a,b,c,表示银行卡 a 比银行卡 b 至多多 c元。
如果每行第一个数是 3,接下来有两个整数 a,b,表示银行卡 a 和 b 里的存款一样多。(1≤n,m,a,b,c≤10000)
Output
如果存在某种情况与蒜头君的记忆吻合,输出Yes,否则输出No。Sample Input 1
3 3
3 1 2
1 1 3 1
2 2 3 2
Sample Output 1Yes
很明显,题目中出现了几个约束条件:
银行卡 a 比银行卡 b 至少多 c 元。
银行卡 a 比银行卡 b 至多多 c 元。
银行卡 a 和银行卡 c 里的存款一样多。转化为不等式方程组:
a-b>=c
a-b<=c
a=c找到了解题的关键,然后将差分约束转化为最短路求解 。
#include<bits/stdc++.h> using namespace std; const int maxn=10100; const int inf=0x3f3f3f3f; int n,m; struct node{ int v,w; node(){ } node(int _v,int _w){ v=_v; w=_w; } }; vector <node> g[maxn]; int dst[maxn]; queue <int> qu; bool inq[maxn]; int cnt[maxn]; int add(int u,int v,int w){ g[u].push_back(node(v,w)); // g[v].push_back(node()); } int spfa(int u){ memset(inq,0,sizeof inq); memset(dst,inf,sizeof dst); memset(cnt,0,sizeof cnt); dst[u]=0; qu.push(u); inq[u]=1; cnt[u]=1; while(!qu.empty()){ u=qu.front(); qu.pop(); inq[u]=0; for(int i=0;i<g[u].size();i++){ int v=g[u][i].v; int w=g[u][i].w; if(dst[v]>dst[u]+w){ dst[v]=dst[u]+w; if(!inq[v]){ qu.push(v); inq[v]=1; cnt[v]++; if(cnt[v]>n+1){ return 0; } } } } } return 1; } int main(){ cin >> n >> m; for(int i=0;i<m;i++){ int d,a,b,c; cin >> d; if(d==1){ cin >>a>>b>>c; g[a].push_back(node(b,-c)); }else if(d==2){ cin >>a>>b>>c; g[b].push_back(node(a,-c)); }else{ cin >>a>>b; g[a].push_back(node(b,0)); g[b].push_back(node(a,0)); } } for(int i=1;i<=n;i++){ add(0,i,0); } if(spfa(0)){ cout << "Yes"<<endl; }else{ cout << "No"; } return 0; }
蒜头君当大厨
Description 蒜头君苦练厨艺,终于成为了某高档酒店的大厨。 每天上班,蒜头君会被要求做 n 份菜。既然是高档酒店,那么客人们当然是很讲究的,尤其对于上菜的时间有很多要求。客人们的要求被分成下列四种: 菜品 a 的上菜时间必须比菜品 b 的上菜时间早 d 分钟或者更早。 菜品 a 的上菜时间必须比菜品 b 的上菜时间迟 d 分钟或者更迟。 菜品 a 的上菜时间在 d 分钟以后(包含 d 分钟)。 菜品 a 的上菜时间在 d 分钟之前(包含 d 分钟)。 蒜头君的上班时间记为 0 分钟。为了节约时间,在满足客人们要求的情况下,蒜头君希望最后上的一道菜的时间尽可能的早。(每道菜的上菜时间必须不早于蒜头君的上班时间) Input 第一行输入一个整数 n,表示一共需要上 n 道菜。 第二行输入一个整数 m,表示客人们的要求数量。 接下里 m 行,每行先输入一个整数 op。 如果 op=1,表示描述里的第 1 种要求,后面跟着三个整数 a,b,d。 如果 op=2,表示描述里的第 2 种要求,后面跟着三个整数 a,b,d。 如果 op=3,表示描述里的第 3 种要求,后面跟着两个整数 a,d。 如果 op=4,表示描述里的第 4 种要求,后面跟着两个整数 a,d。 Output 如果蒜头君能满足客人们的要求,输出最后一道菜的上菜时间;否则输出一行 'I can't'。 数据范围和约定 对于所有的数据:1≤n,m≤20000,1≤∣d∣≤10000 ,1≤a,b≤n,a≠b。 样例解释 1 1,2,3 的上菜时间分别为 0,2,12,这样能满足输入客人们的所有要求,并且时间最短。 Sample Input 1 3 5 2 3 2 10 2 2 1 2 2 3 2 5 1 2 3 7 3 3 9 Sample Output 1 12 Sample Input 2 3 4 3 1 3 2 3 1 9 2 1 3 -1 1 1 2 5 Sample Output 2 I can't Sample Input 3 17 20 2 6 3 -21 1 8 2 54 3 7 -95 4 11 44 1 5 15 40 3 9 1 3 3 30 3 8 23 2 9 12 -15 4 13 61 2 3 7 31 1 5 10 -15 2 16 1 43 2 12 3 -79 2 14 16 -51 3 6 48 4 7 0 2 10 11 -59 2 12 17 -29 3 4 10 Sample Output 3 77
与蒜头君的银行卡差不多,都是找到差分约束条件:
菜品 a 的上菜时间必须比菜品 b 的上菜时间早 d 分钟或者更早。菜品 a 的上菜时间必须比菜品 b 的上菜时间迟 d 分钟或者更迟。
菜品 a 的上菜时间在 d 分钟以后(包含 d 分钟)。
菜品 a 的上菜时间在 d 分钟之前(包含 d 分钟)。
#include<bits/stdc++.h> using namespace std; const int maxn=20010; int n,m; struct node{ int v,w; node(){ } node(int _v,int _w){ v=_v; w=_w; } }; vector <node> g[maxn]; int dst[maxn]; queue <int> qu; bool inq[maxn]; int cnt[maxn]; int flag; int add(int u,int v,int w){ g[u].push_back(node(v,w)); // g[v].push_back(node()); } void spfa(int u){ memset(inq,0,sizeof inq); memset(dst,0x80,sizeof dst); memset(cnt,0,sizeof cnt); dst[u]=0; qu.push(u); inq[u]=1; cnt[u]=1; while(!qu.empty()){ u=qu.front(); qu.pop(); inq[u]=0; for(int i=0;i<g[u].size();i++){ int v=g[u][i].v; int w=g[u][i].w; if(dst[v]<dst[u]+w){ dst[v]=dst[u]+w; if(!inq[v]){ qu.push(v); inq[v]=1; cnt[v]++; if(cnt[v]>n+1){ return; } if(cnt[v]==n+1){ flag=1; } } } } } return; } int main(){ cin >> n >> m; for(int i=0;i<m;i++){ int d,a,b,c; cin >> d; if(d==1){ cin >>a>>b>>c; g[a].push_back(node(b,c)); }else if(d==2){ cin >>a>>b>>c; g[b].push_back(node(a,c)); }else if(d==3){ cin >>a>>b; g[0].push_back(node(a,b)); }else{ cin >>a>>b; g[0].push_back(node(0,-b)); } } for(int i=1;i<=n;i++){ add(0,i,0); } int ans=0; spfa(0); if(flag){ cout<<"I can't"; return 0; } for(int i=1;i<=n;i++){ ans=max(ans,dst[i]); } cout << ans; return 0; }
更多相关内容 -
Bellman-Ford算法与差分约束系统.ppt
2014-07-12 17:22:13Bellman-Ford算法与差分约束系统 -
差分约束
2019-03-28 18:22:18一:差分约束的定义 差分约束系统(system of difference constraints),是求解关于一组变数的特殊不等式组之方法。如果一个系统由n个变量和m个约束条件组成,其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,...一:差分约束的定义
差分约束系统(system of difference constraints),是求解关于一组变数的特殊不等式组之方法。如果一个系统由n个变量和m个约束条件组成,其中每个约束条件形如xj-xi<=bk(i,j∈[1,n],k∈[1,m]),则称其为差分约束系统(system of difference constraints)。亦即,差分约束系统是求解关于一组变量的特殊不等式组的方法。
通俗一点地说,差分约束系统就是一些不等式的组,而我们的目标是通过给定的约束不等式组求出最大值或者最小值或者差分约束系统是否有解。
比如:
二:差分约束的求解
分约束系统可以转化为图论来解决,对应于上面的不等式组,如果要求出x3-x0的最大值的话,叠加不等式可以推导出x3-x0<=7,最大值即为7,我们可以通过建立一个图,包含6个顶点,对每个xj-xi<=bk,建立一条i到j的有向边,权值为bk。通过求出这个图的x0到x3的最短路可以知道也为7,这是巧合吗?并不是。
之所以差分约束系统可以通过图论的最短路来解,是因为xj-xi<=bk,会发现它类似最短路中的三角不等式d[v] <=d[u]+w[u,v],即d[v]-d[u]<=w[u,v]。而求取最大值的过程类似于最短路算法中的松弛过程。
三角不等式:(在此引用大牛的博客)
B - A <= c (1)
C - B <= a (2)
C - A <= b (3)
如果要求C-A的最大值,可以知道max(C-A)= min(b,a+c),而这正对应了下图中C到A的最短路。
因此,对三角不等式加以推广,变量n个,不等式m个,要求xn-x1的最大值,便就是求取建图后的最短路。
同样地,如果要求取差分约束系统中xn-x1的最小值,便是求取建图后的最长路。最长路可以通过spfa求出来,只需要改下松弛的方向即可,即if(d[v] < d[u] + dist(u,v)) d[v] = d[u] + dist(u,v)。当然我们可以把图中所有的边权取负,求取最短路,两者是等价的。
最后一点,建图后不一定存在最短路/最长路,因为可能存在无限减小/增大的负环/正环,题目一般会对应于不同的输出。判断差分约束系统是否存在解一般判环即可。
三:差分约束的应用
差分约束系统的应用很广,都会有一定的背景,我们只需要根据题意构造出差分约束系统,然后再根据题目的要求求解就行了。
一般题目会有三种情况:(1)、求取最短路 (2)、求取最长路 (3)、判断差分约束系统的解是否存在
当然这三种也可能会相互结合。
差分约束系统的解法如下:
1、 根据条件把题意通过变量组表达出来得到不等式组,注意要发掘出隐含的不等式,比如说前后两个变量之间隐含的不等式关系。
2、 进行建图:
首先根据题目的要求进行不等式组的标准化。
(1)、如果要求取最小值,那么求出最长路,那么将不等式全部化成xi – xj >= k的形式,这样建立j->i的边,权值为k的边,如果不等式组中有xi – xj > k,因为一般题目都是对整形变量的约束,化为xi – xj >= k+1即可,如果xi – xj = k呢,那么可以变为如下两个:xi – xj >= k, xi – xj <= k,进一步变为xj – xi >= -k,建立两条边即可。
(2)、如果求取的是最大值,那么求取最短路,将不等式全部化成xi – xj <= k的形式, 这样建立j->i的边,权值为k的边,如果像上面的两种情况,那么同样地标准化就行了。
(3)、如果要判断差分约束系统是否存在解,一般都是判断环,选择求最短路或者最长路求解都行,只是不等式标准化时候不同,判环地话,用spfa即可,n个点中如果同一个点入队超过n次,那么即存在环。
值得注意的一点是:建立的图可能不联通,我们只需要加入一个超级源点,比如说求取最长路时图不联通的话,我们只需要加入一个点S,对其他的每个点建立一条权值为0的边图就联通了,然后从S点开始进行spfa判环。最短路类似。
3、 建好图之后直接spfa或bellman-ford求解,不能用dijstra算法,因为一般存在负边,注意初始化的问题。
---------------------
本博客有相关习题
-
差分约束系统
2013-05-22 14:19:28差分约束系统 -
差分约束系统详解
2013-03-12 16:54:55差分约束系统(system of difference constraints)详解,解释了如何实现该算法及算法复杂度。 -
差分约束系统学习笔记
2018-05-08 21:03:21差分约束系统 一、预备知识 最短路基本性质 #define inf 0x3fffffff #define M 1005 //最大点数 struct edge{ int v, w, next; }e[10005]; //估计好有多少条边 int pre[M], cnt, dist[M], n; bool inq[M...一、预备知识
最短路基本性质
#define inf 0x3fffffff #define M 1005 //最大点数 struct edge{ int v, w, next; }e[10005]; //估计好有多少条边 int pre[M], cnt, dist[M], n; bool inq[M]; //注意初始化 void init () { cnt = 0; memset (pre, -1, sizeof(pre)); } //注意双向加边 void addedge (int u, int v, int w) //加边函数,慢慢模拟就会明白的 { e[cnt].v = v; e[cnt].w = w; e[cnt].next = pre[u]; //接替已有边 pre[u] = cnt++; //自己前插成为u派生的第一条边 } void spfa (int u) { int v, w, i; for (i = 1; i <= n; i++) //对于从1到n的编号 dist[i] = inf, inq[i] = false; dist[u] = 0; queue<int> q; q.push (u); inq[u] = true; while (!q.empty()) { u = q.front(); q.pop(); inq[u] = false; for (i = pre[u]; i != -1; i = e[i].next) { w = e[i].w; v = e[i].v; if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; if (!inq[v]) { q.push (v); inq[v] = true; } } } } }
如果图中不存在负权回路,则当算法结束以后,对于边 < x , y > <x,y> <x,y> 有 d i s [ y ] ≤ d i s [ x ] + w dis[y]\le dis[x]+w dis[y]≤dis[x]+w ,即 d i s [ y ] − d i s [ x ] ≤ w dis[y]-dis[x] \le w dis[y]−dis[x]≤w 成立。
二、什么是差分约束系统
对于一组不等式:
{ x 1 − x 2 ≤ 0 x 1 − x 5 ≤ 1 x 2 − x 5 ≤ 1 x 3 − x 1 ≤ 5 x 4 − x 1 ≤ 4 x 4 − x 3 ≤ − 1 x 5 − x 3 ≤ − 3 x 5 − x 4 ≤ − 3 \left\{\begin{matrix} x_1-x_2 \le 0 \\ x_1-x_5 \le 1 \\ x_2-x_5 \le 1 \\ x_3 -x_1 \le 5 \\ x_4-x_1 \le 4 \\ x_4-x_3 \le -1 \\ x_5-x_3 \le -3 \\ x_5-x_4 \le -3 \end{matrix}\right. ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧x1−x2≤0x1−x5≤1x2−x5≤1x3−x1≤5x4−x1≤4x4−x3≤−1x5−x3≤−3x5−x4≤−3
特点是全都是两个未知数的差小于等于某个常数(大于等于也可以,因为左右乘 − 1 -1 −1 就可以化成小于等于的形式),这样的不等式组称作差分约束系统。这个不等式组要么无解,要么就有无限组解。因为如果存在一组解 { x 1 , x 2 , . . , x n } \{x_1,x_2,..,x_n\} {x1,x2,..,xn} 的话,那么对于任何一个常数 k k k 有 { x 1 + k , x 2 + k , . . , x n + k } \{x_1+k,x_2+k,..,x_n+k\} {x1+k,x2+k,..,xn+k} 也肯定是一组解,因为任何两个数加上一个数以后,它们之间的关系(差)是不变的,这个差分约束系统中的所有不等式都不会被破坏。
三、差分约束系统与最短路径
差分约束系统的解法用到了单源最短路径问题中的三角形不等式。即对有向图中任意一条边 < u , v > <u,v> <u,v> 都有: d i s [ v ] ≤ d i s [ u ] + l e n [ u ] [ v ] dis[v] \le dis[u]+len[u][v] dis[v]≤dis[u]+len[u][v] ,其中 d i s [ u ] dis[u] dis[u] 和 d i s [ v ] dis[v] dis[v] 是从源点分别到点 u u u 和点 v v v 的最短路径的长度, l e n [ u ] [ v ] len[u][v] len[u][v] 是边 < u , v > <u,v> <u,v> 的长度值。
这是显然的:如果存在顶点 u u u 到顶点 v v v 的有向边,那么从源点到顶点 v v v 的最短路径长度 小于等于从源点到顶点 u u u 的最短路径长度加上边 < u , v > <u,v> <u,v> 的长度值。
显然上述的不等式就是所描述的,也和差分约束系统中的不等式相同,因此就可以把差分约束系统转化成一张图。
四、构图求解
4.1 基本构图
每个未知数 x i x_i xi 对应图中的一个顶点 v i v_i vi ,把所有的不等式都化成图中的一条边,对于不等式 x i − x j ≤ y x_i-x_j \le y xi−xj≤y 化成三角形不等式 x i ≤ x j + y x_i \le x_j+y xi≤xj+y 就可以化成边 < v j , v i > <v_j,v_i> <vj,vi> 权值为 y y y 。最后在这张图上求一遍单源最短路,这些三角不等式就全部满足了,因为它是最短路问题的基本性质。
不等式组 ( 1 ) (1) (1) 转化成
4.2 求解
以 1 1 1 为起点,则起点到各个顶点的最短距离为 d i s [ 1 ] = 0 , d i s [ 2 ] = 2 , d i s [ 3 ] = 5 , d i s [ 4 ] = 4 , d i s [ 5 ] = 1 dis[1]=0,dis[2]=2,dis[3]=5,dis[4]=4,dis[5]=1 dis[1]=0,dis[2]=2,dis[3]=5,dis[4]=4,dis[5]=1 则得到解 x 1 = 0 , x 2 = 1 , x 3 = 5 , x 4 = 4 , x 5 = 1 x_1=0,x_2=1,x_3=5,x_4=4,x_5=1 x1=0,x2=1,x3=5,x4=4,x5=1
以 3 3 3 为起点,则起点到各个顶点的最短距离为 d i s [ 1 ] = − 5 , d i s [ 2 ] = − 5 , d i s [ 3 ] = 0 , d i s [ 4 ] = − 1 , d i s [ 5 ] = − 4 dis[1]=-5,dis[2]=-5,dis[3]=0,dis[4]=-1,dis[5]=-4 dis[1]=−5,dis[2]=−5,dis[3]=0,dis[4]=−1,dis[5]=−4 则得到解 x 1 = − 5 , x 2 = − 4 , x 3 = 0 , x 4 = − 1 , x 5 = − 4 x_1=-5,x_2=-4,x_3=0,x_4=-1,x_5=-4 x1=−5,x2=−4,x3=0,x4=−1,x5=−4
以不同顶点作为起点会得到不同的解,但这些解都一定合理。
- 什么情况下无解? 存在负权回路!
4.3 增加源点
具体实现时,往往在原图上附加一个顶点,这个顶点与每个顶点都连接一条权值为 0 0 0 的边,以上述不等式为例,也就是新加入一个未知数 x 0 x_0 x0 ,然后对每个未知数都对 x 0 x_0 x0 加一个不等式,得到
这样的不等式组 ( 2 ) (2) (2) ,化成顶点图
图中每一条边都代表差分约束系统的一个不等式。现在以 v 0 v_0 v0 为源点,求单源最短路,最终得到的 v 0 v_0 v0 到 v i v_i vi 的最短路径长度就是 x i x_i xi 的一个解。如图中 v 0 v_0 v0 到其他各个顶点的最短距离分别是 { − 5 , − 3 , 0 , − 1 , − 4 } \{-5,-3,0,-1,-4\} {−5,−3,0,−1,−4} ,因此满足上述不等式的一组解就是 { x 1 , x 2 , x 3 , x 4 , x 5 } = { − 5 , − 3 , 0 , − 1 , − 4 } \{x_1,x_2,x_3,x_4,x_5\}=\{-5,-3,0,-1,-4\} {x1,x2,x3,x4,x5}={−5,−3,0,−1,−4} 。当然把每个数都加上 10 10 10 也是一组解 { 5 , 7 , 10 , 9 , 6 } \{5,7,10,9,6\} {5,7,10,9,6} ,但是这组解只满足不等式组 ( 1 ) (1) (1) ,也就是原先的差分约束系统,而不满足不等式组 ( 2 ) (2) (2) ,也是我们后来加上的那些不等式。当然这是无关紧要的,因为 x 0 x_0 x0 本来就是个局外人,并不在乎它。
对于上面例子而言,它代表的解 x 0 x_0 x0 值也在其中也就是 x 0 = 0 x_0=0 x0=0 。但是 x 0 x_0 x0 的值是无可争议的,既然是以它作为源点求最短路径,那么源点到它的最短路径当然是 0 0 0 了,因此,我们解这个差分约束系统无形中存在一个条件 x 0 = 0 x_0=0 x0=0 ,那么它有什么用呢?可以限制所有的未知数的解都不大于0 。
- 一个有趣的结论:当我们一开始就把 x 0 x_0 x0 的解死定为 A A A 的时候,所有未知数的解都不会大于 A A A (一开始把 d i s [ 0 ] = A dis[0]=A dis[0]=A)
五、例题
5.1 最大身高
Description
FJ的 N ( 1 ≤ N ≤ 10 , 000 ) N(1\le N \le 10,000) N(1≤N≤10,000) 头奶牛站成一排,并从左到右被编号为 1.. N 1..N 1..N 。每头奶牛都有一个正整数的身高,具体的值FJ暂时保密,但会告诉你它们当中最高的一头的编号 I I I 和身高 H ( 1 ≤ H ≤ 1 0 6 ) H\ (1 \le H \le 10^6) H (1≤H≤106) 的值。
FJ制作一张包含 R ( 0 ≤ R ≤ 1 0 4 ) R\ (0 \le R \le 10^4) R (0≤R≤104) 行的列表,每行的都是形如"第17号奶牛能看到第34号奶牛”,其意义是34号奶牛的身高不低于17号奶牛的身高,并且在17号和34号之间的奶牛的身高都严格低于17号奶牛的身高。
请你确定奶牛每头奶牛的最大可能的身高,我们保证给出的数据都是正确的,并且一定有满足限制条件的解。
Input
第1行:包含四个用空格分开的整数:N, I, H 和 R
第2…R+1行:每行包含两个用空格分开的整数A和B(1 <= A,B <= N),表示奶牛A能看到奶牛B
Output
第1…N行:第i行包含一个整数,表示第i头奶牛的最大身高。
Sample Input
9 3 5 5 1 3 5 3 4 3 3 7 9 8
Sample Output
5 4 5 3 4 4 5 5 5
Solution
{ x 1 − x 3 ≤ 0 x 2 − x 1 ≤ − 1 x 5 − x 3 ≤ 0 x 4 − x 5 ≤ − 1 x 4 − x 3 ≤ 0 x 3 − x 7 ≤ 0 x 4 − x 3 ≤ − 1 x 5 − x 3 ≤ − 1 x 6 − x 3 ≤ − 1 x 9 − x 8 ≤ 0 \left\{\begin{matrix} x_1-x_3 \le 0\\ x_2-x_1\le -1\\ x_5-x_3\le 0\\ x_4-x_5\le -1\\ x_4-x_3\le 0\\ x_3-x_7\le 0\\ x_4-x_3\le -1\\ x_5-x_3\le -1\\ x_6-x_3\le -1\\ x_9-x_8\le 0 \end{matrix}\right. ⎩⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎨⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎪⎧x1−x3≤0x2−x1≤−1x5−x3≤0x4−x5≤−1x4−x3≤0x3−x7≤0x4−x3≤−1x5−x3≤−1x6−x3≤−1x9−x8≤05.2 糖果
Description
幼儿园里有N个小朋友,lxhgww老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。但是小朋友们也有嫉妒心,总是会提出一些要求,比如小明不希望小红分到的糖果比他的多,于是在分配糖果的时候,lxhgww需要满足小朋友们的K个要求。幼儿园的糖果总是有限的,lxhgww想知道他至少需要准备多少个糖果,才能使得每个小朋友都能够分到糖果,并且满足小朋友们所有的要求。
Input
输入的第一行是两个整数N,K。
接下来K行,表示这些点需要满足的关系,每行3个数字,X,A,B。
如果X=1,表示第A个小朋友分到的糖果必须和第B个小朋友分到的糖果一样多;
如果X=2,表示第A个小朋友分到的糖果必须少于第B个小朋友分到的糖果;
如果X=3,表示第A个小朋友分到的糖果必须不少于第B个小朋友分到的糖果;
如果X=4,表示第A个小朋友分到的糖果必须多于第B个小朋友分到的糖果;
如果X=5,表示第A个小朋友分到的糖果必须不多于第B个小朋友分到的糖果;
Output
输出一行,表示lxhgww老师至少需要准备的糖果数,如果不能满足小朋友们的所有要求,就输出
-1
。Sample Input
7 7 1 4 5 2 1 4 5 3 5 4 1 3 3 1 2 2 2 3 4 6 7
Sample Output
17
Solution
本题对于每个小朋友要求都能分到糖果,也就是说,每个小朋友的糖果数应该要大于 1 1 1 ,怎么把不等式组的解都变为 ≥ 1 ≥1 ≥1 ?
- 重要结论:以 x i − x j ≤ y x_i-x_j\le y xi−xj≤y 为约束条件,建图求最短路后得到的是最大解。所有的解都不大于且尽可能逼近 d i s [ x 0 ] dis[x_0] dis[x0] 。
若有 x i − x j ≤ y x_i-x_j \le y xi−xj≤y 可在图中连一条 x j x_j xj 出发指向 x i x_i xi 的有向边,权值为 y y y ,再添加一个源点 x 0 x_0 x0 指向各个顶点 x 1 , x 2 , . . , x n x_1,x_2,..,x_n x1,x2,..,xn 权值为 0 0 0 。若一开始就把 d i s [ x 0 ] dis[x_0] dis[x0] 的值定死为 A A A 再求最短路,那么求出来的解都是不大于 A A A 且与 A A A 接近的最大解,也就是 x i ≤ A x_i \le A xi≤A ,那么我们设 d i s [ x 0 ] = − 1 dis[x_0]=-1 dis[x0]=−1 ,所有未知数解直接取绝对值,行吗?答案是它取绝对值以后不难满足不等式组 ( 1 ) (1) (1) ,通过一些讨论发现,直接在所有未知数上加上某个常数来解决此题是不可行的。
正确接啊应该是,对于这题,按照相反的建图方式,
若有 x i − x j ≥ y x_i-x_j ≥y xi−xj≥y 则在图中连上一条 < x j , x i > <x_j,x_i> <xj,xi> 的有向边,权值为 y y y ,再以 x 0 x_0 x0 为起点,求单源最长路(无正权环前提下),求出的起点到各个点的距离就是不等式组 ( 2 ) (2) (2) 的一组解。若一开始把 d i s [ x 0 ] dis[x_0] dis[x0] 定值为 A A A 再求最长路,那么求出的其他点的 d i s [ x i ] dis[x_i] dis[xi] 的值一定不会小于 A A A ,并且,求出的值是不小于它且最接近它的一组,也就是最小解。
六、总结
查分约束求解不等式组分为两种方法:最短路和最长路。
其中最短路对应最大解,最长路对应最小解,特别的,若有 x i = x j x_i=x_j xi=xj 的情况,建图时候,从 x i x_i xi 出发连一条权值为 0 0 0 的边到 x j x_j xj ,同时也建一条同等权值的反向边。
对于许多复杂的问题,我们通常选择将不够清晰、难以处理的模型转化为容易理解、易于处理的模型。就像用已知的知识作为工具去探索未知领域一样,联想、发散、转化将成为相当有用的武器。
-
bellmanford算法与差分约束系统.ppt
2020-11-15 06:41:44Bellman-Ford算法 与差分约束系统;单源最短路径问题;精品资料; 你怎么称呼老师 如果老师最后没有总结一节课的重点的难点你是否会认为老师的教学方法需要改进 你所经历的课堂是讲座式还是讨论式 教师的教鞭 不怕太阳... -
差分约束算法总结
2017-06-03 01:48:34差分约束系统 一、概念 如果一个系统由n个变量和m个约束条件组成,形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),则称其为差分约束系统。 二、引例 给定n个变量和m个不等式,每个不等式的形式为 x[i] - x[j] ...差分约束系统
一、概念
如果一个系统由n个变量和m个约束条件组成,形成m个形如ai-aj≤k的不等式(i,j∈[1,n],k为常数),则称其为差分约束系统。
二、引例
给定n个变量和m个不等式,每个不等式的形式为 x[i] - x[j] <= a[k] (0 <= i, j < n, 0 <= k < m, a[k]已知),求 x[i] - x[j] 的最大值 。例如当n = 4,m = 5,给出如下图所示的不等式组,求x3 - x0的最大值。一般思路:我们可以尝试把几个不等式组合得到最后我们要求的式子,于是这些式子里最小的那个就是答案。比如,在这个例子中:(3) ==》 x3 - x0<=4;(1)、(4)、(5) ==》 x3 - x0<=5;(2)、(5) ==》 x3 - x0<=3;所以最后结果就是3.在这个过程中,我们是否想到这种方法与我们已经学的一种算法有所联系,是的,就是最短路算法。
三、差分约束与最短路模型
1、与最短路模型的联系
先给出结论:求解差分约束系统,都可以转化成图论的单源最短路径(或最长路径)问题。
我们观察上面例子中的不等式,都是x[i] - x[j] <= a[k],可以进行移项,成为x[i] <= x[j] + a[k],我们令a[k] = w(j, i),dis[i]=x[i],并使i=v,j=u,那么原始就变为:dis[u]+w(u,v)>=dis[v],于是可以联想到最短路模型中的一部分代码
if(dis[u]+w(u,v)<=dis[v]) { dis[v]=dis[u]+w(u,v); }
这不正与松弛操作相似吗?
但是好像不等号方向刚好相反,但其实这并不矛盾
上面的代码要实现的是使dis[u]+w(u,v)>dis[v],而对于不等式,我们进行建边的操作:对于每个不等式 x[i] - x[j] <= a[k],对结点 j 和 i 建立一条 j -> i的有向边,边权为a[k],求x[n-1] - x[0] 的最大值就是求 0 到n-1的最短路,两者刚好吻合。所以求解差分约束问题就转化为了最短路问题。
2.问题解的存在性
由于在求解最短路时会出现存在负环或者终点根本不可达的情况,在求解差分约束问题时同样存在
(1)、存在负环
如果路径中出现负环,就表示最短路可以无限小,即不存在最短路,那么在不等式上的表现即X[n-1] - X[0] <= T中的T无限小,得出的结论就是 X[n-1] - X[0]的最大值不存在。在SPFA实现过程中体现为某一点的入队次数大于节点数。(貌似可以用sqrt(num_node)来代替减少运行时间)
(2)、终点不可达
这种情况表明X[n-1]和X[0]之间没有约束关系,X[n-1] - X[0]的最大值无限大,即X[n-1]和X[0]的取值有无限多种。在代码实现过程中体现为dis[n-1]=INF。
3、不等式组的转化
做题时可能会遇到不等式中的符号不相同的情况,但我们可以对它们进行适当的转化
(1)方程给出:X[n-1]-X[0]>=T ,可以进行移项转化为: X[0]-X[n-1]<=-T。
(2)方程给出:X[n-1]-X[0]<T, 可以转化为X[n-1]-X[0]<=T-1。
(3)方程给出:X[n-1]-X[0]=T,可以转化为X[n-1]-X[0]<=T&&X[n-1]-X[0]>=T,再利用(1)进行转化即可
4、应用
对于不同的题目,给出的条件都不一样,我们首先需要关注问题是什么,如果需要求的是两个变量差的最大值,那么需要将所有不等式转变成"<="的形式,建图后求最短路;相反,如果需要求的是两个变量差的最小值,那么需要将所有不等式转化成">=",建图后求最长路。
5、相关题目链接
(1)、POJ 1716 Integer Intervals
(2)、HDOJ 3666 THE MATRIX PROBLEM
-
浅谈差分约束算法
2018-03-09 00:08:16参考:http://www.cppblog.com/menjitianya/archive/2015/11/19/212292.html (理论部分) https://www.cnblogs.com/zhangmingcheng/p/3929394.html (题集举例)差分约束系统有两种方式可以求解,最短路和最长路... -
图论- 差分约束系统.rar
2021-09-16 22:49:38图论- 差分约束系统.rar -
差分约束详解
2016-10-15 20:56:42差分约束的经典应用 1、线性约束 2、区间约束 3、未知条件约束 五、 差分约束 题集整理 一、引例 1、一类不等式组的解 给定n个变量和m个... -
冯威-浅析差分约束系统.ppt
2021-09-17 19:11:23冯威-浅析差分约束系统.ppt -
Acwing 362.区间(差分约束)
2021-10-29 20:03:051} >= c_i xbi−xai−1>=ci 因为 a , b a,b a,b 都是从 0 开始的,不方便使用前缀和,所以将所有 a , b a,b a,b 整体右移 1 1 1 从 1 1 1 开始 因为要求 Z Z Z 中最少包含多少个数,所以应该用差分约束的最长... -
差分约束系统例题详解[总结].pdf
2021-10-12 03:52:15差分约束系统例题详解[总结].pdf -
bellmanford算法与差分约束系统 _ford法计算最短路径
2020-09-05 07:47:25Bellman-Ford算法 与差分约束系统;单源最短路径问题;Dijkstra算法的局限性;Dijkstra算法的局限性;Dijkstra算法的局限性;错误结果的原因;Bellman-Ford算法思想;Bellman-Ford算法思想;Bellman-Ford算法流程;时间复杂度... -
【差分约束系统】
2018-04-12 09:54:25如果一个系统由n个变量和m个约束条件组成,形成m个形如aiaia_i-ajaja_j≤kkk的不等式(i,j∈[1,n],ki,j∈[1,n],ki,j∈[1,n],k为常数),则称其为差分约束系统(systemof difference constraints)。亦即,差分约束系统是... -
1751【差分约束】Intervals(区间)[借鉴].pdf
2021-10-19 00:57:591751【差分约束】Intervals(区间)[借鉴].pdf -
Acwing 368.银河(tarjan缩点优化差分约束)
2021-11-25 21:38:31tarjan求scc优化差分约束 差分约束的两种模型:求最小值和最大值 分别对应最长路和最短路。 对于最长路模型,判断是否无解的依据是图中有没有正环。考虑tarjan算法缩点后的某个scc,如果这个scc中有某条边权值大于0 ... -
差分约束系统(最短路径问题)
2017-04-26 17:08:38差分约束系统 X1 - X2 X1 - X5 X2 - X5 X3 - X1 X4 - X1 X4 - X3 X5 - X3 X5 - X4 不等式组(1) 全都是两个未知数的差小于等于某个常数(大于等于也可以,因为左右乘以-1就可以化成小于等于)。这样的... -
冯威《数与图的完美结合——浅析差分约束系统》
2012-07-08 16:11:30冯威《数与图的完美结合——浅析差分约束系统》 -
差分约束系统详解.doc
2011-02-06 18:49:20差分约束系统详解(system of difference constraints) -
算法合集之《浅析差分约束系统》_基于lm算法的约束重构
2019-12-12 00:34:26算法合集之《浅析差分约束系统》.ppt -
差分约束系统详解(转化为最短路)
2014-10-02 09:59:16给定一个差分约束系统Ax≤b,相应的约束图是一个带权有向图G=(V,E),其中V={v0,v1,…,vn},而且E={ (vi,vj) : xj-xi≤bk是一个约束}∪{ (v0,v1) , (v0,v2) , … , (v0,vn) }。引入附加顶点v0是为了保证其他每个... -
|算法讨论|差分约束 学习笔记
2017-02-11 16:20:29[差分约束]poj 1201:用最短路算法求最长路求差分约束模板及讲解差分约束就是给出一些形如x−y≥cx-y \ge c的约束,问你是否有解,或求最大、最小解。该问题可以转化为图上最短路问题。1、求最大差 建立形如 A−B的... -
差分约束(看不太懂但是觉得挺有用的)
2015-07-13 14:41:51差分约束系统中,如果按照最短路形式d[u]-d[v] ...反之,按照最长路形式d[u]-d[v]>=w[v,u]建图,所有值达到最小 ...一直不知道差分约束是什么类型题目,最近在写最短路问题就顺带看了下,原来就是给出一些形如x