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}$ 大小的最大值(也就是不相同的数最多)。

题解

首先我们按照差分约束将图建出来,然后判出无解。
我们考虑如何构造出一组最大的解:我们需要注意到图上 $u$ 到 $v$ 的路径对应了一个 $u$ 和 $v$ 的不等关系限制。那么我们考虑怎么样的点不会相互被限制呢?可以发现 SCC 内的点是互相被限制的,于是我们缩点,答案就是每个 SCC 内的最短路的最大值 + 1。因为不同 SCC 内的点取值集可以不交,同一 SCC 内对于一条最短路一定能分布出递增的点权,其他的按照限制填。
注意这个图可能不连通 Orz

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/870
如文中无特殊声明,本文采用 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

「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}$ 大小的最大值(也就是不相同…
扫描二维码继续阅读
2019-10-12
标签
近期评论