差分约束系统学习笔记

xiaoxiao2021-02-28  6

一、预备知识

最短路基本性质
#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. x1x20x1x51x2x51x3x15x4x14x4x31x5x33x5x43 特点是全都是两个未知数的差小于等于某个常数(大于等于也可以,因为左右乘 − 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 xixjy 化成三角形不等式 x i ≤ x j + y x_i \le x_j+y xixj+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(1N10,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 (1H106) 的值。

​ FJ制作一张包含 R   ( 0 ≤ R ≤ 1 0 4 ) R\ (0 \le R \le 10^4) R (0R104) 行的列表,每行的都是形如"第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. x1x30x2x11x5x30x4x51x4x30x3x70x4x31x5x31x6x31x9x80

5.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 xixjy 为约束条件,建图求最短路后得到的是最大解。所有的解都不大于且尽可能逼近 d i s [ x 0 ] dis[x_0] dis[x0]

若有 x i − x j ≤ y x_i-x_j \le y xixjy 可在图中连一条 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 xiA ,那么我们设 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 xixjy 则在图中连上一条 < 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 ,同时也建一条同等权值的反向边。

对于许多复杂的问题,我们通常选择将不够清晰、难以处理的模型转化为容易理解、易于处理的模型。就像用已知的知识作为工具去探索未知领域一样,联想、发散、转化将成为相当有用的武器。

转载请注明原文地址: https://www.6miu.com/read-1599990.html

最新回复(0)