CFGYM102394A CCPC2019哈尔滨A Artful Paintings

一眼看过去是差分约束板子题,实际上也就是差分约束板子题。

首先这个题可以对答案进行二分。如果铺x个可行,那么x+1个显然可行,所以我们先二分确定一个x。

然后我们的题目转变成了,能不能在恰好铺x个的情况下构造一组合法方案,根据最短路的松弛条件可知,不等式$x_a+v\leq x_b$等价于从a到b,边权为$-v$的边(最短路存在时,令$x_a$表示源点到a的距离,$x_b$同理,那么$x_a$和$x_b$在作为未知变量的时候一定是满足上述不等式的。)

所以我们可以得到,需要建立以下六种不等式:

1. $x_{n-1}+0\leq x_n$(前缀和不减)
2. $x_n+(-1)\leq x_{n-1}$前缀和要么加1要么不变
3. $x_{l-1}+x\leq x_r$ 区间染色数下限
4. $x_r +(x-M) \leq  x_{l-1}$ 区间外染色数下限
5. $x_0+M\leq x_n$ 一共至少染M个
6. $x_n+(-M)\leq x_0$ 一共至多染M个(与5一起保证恰好染M个)

然后据此建边,其中$M$是我们二分的铺的个数。建出来的图跑一个从n到0的最短路,如果最短路存在(即没有负环),那说明M可行,答案可以考虑进一步缩小。如果存在负环,则说明M不可行。

但是这里的SPFA要注意优化,大概需要一个SLF(Small Label First),即如果待入队节点的已知最短距离小于队列头部节点,则把他扔到队列头部。
然后别用long long,跑的有点慢。

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据