RainAir
My OI Blog
RainAir

差分约束系统
文章归档

「BZOJ2788」Poi2012Festival

题意 今有 $n$ 个变量, $x_1,x_2,\cdots,x_n$,还有 $m1+m2$ 个限制条件: 1. $x_a + 1 = x_b$ 2. $x_c \leq x_d$ 在满足所有限制的前提下,求集合 ${x_i}$ 大小的最大值(也就是不相同的数最多)。 题解 首先我们按照差分约束将图建出来,然后判出无解。 我们考虑…

   48   2019-10-12   48 去吊打作者

差分约束系统学习笔记

差分约束系统,就是给定一些 $ x_i - x_j >= d $ 的不等式,求出其中的一组解。我们可以转化为最短路来解决该类问题。 实现 PS:以下讨论整数情况,浮点数请注意精度。 我们对于每一组 $ x_i - x_j >= d $ 的不等式,从$ j $ 向 $ i $ 连一条长度为d的边。 可能有人…

   513   2018-03-17   513 去吊打作者
标签
近期评论