前言
C++算法与数据结构
本博文代码打包下载
什么是差分约束
x系列是变量,y系列是常量,差分系统由若干如下不等式组成。
x1-x2 <= y1 x2-x3 <= y2 ⋯ \cdots ⋯
可能有负环的最短路
个人习惯:如果存在a指向b的边,则a是b的前置节点,b是a的后续节点。
某差分约束有n个变量(编号从1到n),m个不等式。根据此差分约束建立有向图G。
第一步,n个节点,m条边。每个不等式 x 1 − x 2 < = y 1 都增加边 x 2 → x1 - x2 <=y1都增加边 x2 \rightarrow x1−x2<=y1都增加边x2→x1,边权位y1。
第二步:增加节点0,0到所有节点都有边,边权为0。
差分系统的变量和0到各节点的最短路一一对应。
性质一:差分约束所有的限制,有向图都有。故:有向图的解一定是差分约束的解。差分约束的解不一定是G的最短路。 ⟺ \iff ⟺ 差分系统是G的充分不必要条件。
性质二:有向图无解时,差分约束也无解。存在负环时,有向图无解。不失一般性,以3个节点的环为例。有向图有负环时,差分系统有: x1<=x2+y1 x2<=x3+y2 x3 <=x1+y3 x1 <= x1 + y1+y2+y3 即 0 <= y1+y2+y3,和节点1,2,3是负环矛盾。可以用数学归纳法证明。
性质三:令(a1,a2 ⋯ \cdots ⋯)是有向图的解,则(a1+d,a2+d ⋯ \cdots ⋯)也是差分系统的解。因为:(x1+d)-(x2-d)等于x1-x2。
性质四:在不引入负环的前提下,缩短任意一条边的解仍然是原系统的解。将y1减去正无穷小(此边权变小),构成的新图。如果有解,也是旧系统的解。
推论一:将任何节点i的直接、间接前置节点和i增加一个正数,则新系统的解仍然是老系统的解。如果节点在环上,此环上所有节点都增加。由于环的点都增加了x,故环上的边权不变,故不会引入负环。
性质五:延长任意一条边产生的新解一定不是旧系统的解。产生的新解 x1-x2一定大于y1。
推论二:原始图,如果节点i增加了一个正整数x,则它的直接、间接前置节点都需要增加x或更多。
负环最短路
dis[t][cur]记录最多经过t条边,从0到cur的最短路。
∀ \forall ∀cur ,dis[n][cur] != dis[n-1][cur],说明存在负环。则无解。
第一层循环枚举前置状态,t = 0 to N-1。第二循环枚举各边。
时间复杂度:O(点数边数)
template<class T = int, T iDef = INT_MAX / 2>
class CDisNegativeRing //贝尔曼-福特算法
{
public:bool Dis(int N, vector<tuple<int, int, int>> edgeFromToW, int start) {vector<T> pre(N, iDef);pre[start] = 0;for (int t = 0; t < N; t++) {auto cur = pre;for (const auto& [u, v, w] : edgeFromToW) {cur[v] = min(cur[v], pre[u] + w);}if (t + 1 == N) {for (int i = 0; i < N; i++) {if (pre[i] != cur[i]) { return false; }}}pre.swap(cur);}m_vDis = pre; return true;}vector<T> m_vDis;
};
最长路
对应的差分系统是:x1-x2 >= y1 x2-x3 >=y2 x3-x1 >=y3
如果存在正环,则无解。
可以延长边,不能缩短边。
节点i和它的直接间接前置节点可以减去一个正数,仍然是解。
样例
【差分约束】P5960 差分约束 | 普及+ |
【差分约束】P4878 [USACO05DEC] Layout G | 普及+ |
如果差分系统无解,本题无解。如果有解,求第N个变量减第一个变量的最大值。如果1不是N的前置节点,则N可无限增大,即无穷大。否则就是最短路相减。 | |
【差分约束】P5590 赛车游戏 | 省选- |
本题求边权,任意解,即差分系统的y系列。 | |
【差分约束】 P3275 [SCOI2011] 糖果 | 省选- |
本题求最小正整数解,利用拓扑排序和推论一。 |
扩展阅读
我想对大家说的话 |
---|
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。 |
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作 |
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注 |
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。 |
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。 |
如果程序是一条龙,那算法就是他的是睛 |
失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。