RainAir
My OI Blog
RainAir
差分约束系统学习笔记

差分约束系统,就是给定一些 $ x_i – x_j >= d $ 的不等式,求出其中的一组解。我们可以转化为最短路来解决该类问题。

实现

PS:以下讨论整数情况,浮点数请注意精度。
我们对于每一组 $ x_i – x_j >= d $ 的不等式,从$ j $ 向 $ i $ 连一条长度为d的边。
可能有人会问:如果是其他状态的不等式呢?
我们可以利用以下转换:
1、 $ x_i – x_j >= dist $ 可以转换为 $ x_j – x_i <= -dist $
2、 $ x_i – x_j < dist $ 可以转换为 $ x_i – x_j <= dist – 1 $
3、 $ x_i – x_j == dist$ 可以转换为 $ x_i – x_j <= dist and x_j – x_i <= dist $

跑完后每个结点的dist及为结果。
一般在计算$ x_1 – x_n $最大解时跑最短路,最小解时跑最长路。
如果图中有负环,则无解。

例题

CodeVS4416
给出n个形如 $ x_i – x_j <= d $ 或 $ x_i – x_j >= d $ 的不等式,求一组$ x_1 – x_n $最大的解。
如果无解输出-1,差无限大输出-2。

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/48
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 CSP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

差分约束系统学习笔记
差分约束系统,就是给定一些 $ x_i - x_j >= d $ 的不等式,求出其中的一组解。我们可以转化为最短路来解决该类问题。 实现 PS:以下讨论整数情况,浮点数请注意精度。 我们对于每一组 …
扫描二维码继续阅读
2018-03-17
标签
近期评论