[关闭]
@l1ll5 2018-01-19T14:06:28.000000Z 字数 1824 阅读 1424

差分约束问题浅谈

—— by dsfz l1ll5

图论 最短路 差分约束


写在前面的话

图论我不太会,这个东西我也不太会,但是既然都决定啦,就让我来讲当总书记,所以写了篇这个东西...
晚上赶工的成品...有错误欢迎随时骂我。


有什么用

可以用来解一类不等式组,其中的每个不等式为如下形式:

即两个未知量的差不等于某常数。
显然的,可以发现此处的不等号不等式的形式并不影响,可以通过两遍均乘 来完成转化。

然这样的不等式组要么无解,要么有无数种解,因为当我们求出一组特解 后,将每个未知量置为 后显然也是一组可行解。


数和图的转化

考虑常见的单源最短路算法实现,均考虑到如下的三角形不等式。

若存在边 则一定有:

于是在算法迭代的过程中按此规则多次迭代,即可得到单源最短路的解。
发现这个式子和上式很像,若将 视为一个未知量,则两个问题的形式是完全相同的。

所以对于我们的不等式组,按照如下规则建图:

对于不等式 ,建边 ,权值为

可以发现,当我们求出单源最短路后,这个最短路的解一定满足每个三角形不等式,即满足每条边——原不等式组中每条不等式的限制。
那么让我们愉快的求最短路吧...? 有个问题是发现我们没有原点,即没有一个已知的源点 满足 来让我们启动这个算法。

既然没有困难,就让我们创造困难

一个常见的套路是直接建立虚拟源点 ,对于 ,设立如下不等式组:

我们钦定 ,可以发现 的取值对答案没有影响。因为如果存在一组解,那么存在无数组解,一定存在某组解满足我们钦定的 。如果不存在解,显然多了几条限制更不会有解了...

所以我们可以对这个模型大力最短路,求出的就是一组可行解了。

更进一步,这组可行解是在钦定 情况下的最大解。
如果你理解了以上的内容,可以发现这里的最大解对于每个解和这些解的和而言都取到了最大。并且若存在解必定存在一组这样的最大解。

为什么呢?
考虑最短路算法的迭代流程,首先置 ,按照三角形不等式迭代直至得到解
令最大解为 ,我们置 ,显然直接满足所有三角形不等式,得到解

最短路问题有解则一定有唯一解,否则迭代未稳定,则一定有

这个解的实际意义为,每个未知量均为非正整数时的最大解。
相对的,如果求每个未知量均为非负整数时的最小解,转换最短路模型为最长路模型即可,细节可以自己思考下。

关于无解情况的判定,图中存在负环则无解, dijkstra 算法无法解决这个问题,我们通常采用 SPFA 算法在执行最短路的同时判断负环。

负环怎么判呢? 一个节点在 SPFA 的过程中入队超过 次则存在负环,显然这个判断复杂度是 的...
另一个判断方法是把 SPFA 写成 dfs 版的,这样判断是否重复入栈即可,相对不好卡了一点所以很多时候跑的飞快。


练习

例 1

幼儿♂园里有 老师现在想要给这些小朋友们分配糖果,要求每个小朋友都要分到糖果。但是小朋友们没有许容之心,总是会提出一些要求,比如小明不希望小红分到的糖果比他的多,于是在分配糖果的时候, 需要满足小朋友们的 个要求。幼儿园的糖果总是有限的, 想知道至少需要准备多少个糖果,才能使得每个小朋友都能够分到糖果,并且满足小朋友们所有的要求。

输入的第一行是两个整数
接下来K行,表示这些点需要满足的关系,每行3个数字,
如果 , 表示第 个小朋友分到的糖果必须和第 个小朋友分到的糖果一样多;
如果 , 表示第 个小朋友分到的糖果必须少于第 个小朋友分到的糖果;
如果 , 表示第 个小朋友分到的糖果必须不少于第 个小朋友分到的糖果;
如果 , 表示第 个小朋友分到的糖果必须多于第 个小朋友分到的糖果;
如果 , 表示第 个小朋友分到的糖果必须不多于第 个小朋友分到的糖果;

题目经过魔改,练习建图用。

写出不等式大力跑即可。

BZOJ 2330 [SCOI2011]糖果

例 2

给出一组差分约束系统判断是否存在可行解。

BZOJ 3436 小 K 的农场

例 3

BZOJ 1731 [Usaco2005 dec]Layout 排队布局

没想到什么有意思的题... 就丢出来大家自己去做一做吧...


THX

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注