command_block 的博客

command_block 的博客

[图论记录]ARC117F Gateau

posted on 2021-10-29 09:21:58 | under 未分类 |

题意 : 有一个长为 $2n$ 的环形数组 $A$ ,全为自然数。

给出 $2n$ 条约束,约束 $i$ 形如:从 $A_i$ 开始的半环的和 $\geq B_i$ 。

在满足所有约束的情况下,最小化 $\sum A$ 的值,回答这个最小值。

$n\leq 1.5\times 10^5$ ,时限$\texttt{3s}$。


考虑二分,判定答案是否 $\leq M$ 。

记 $S$ 为 $A$ 的前缀和。

$S$ 合法的充要条件是:

  • $S_{i-1}\leq S_i$

  • $S_0=0,S_{2n}=M$ 即 $S_{2n}-S_0\geq M$

  • 对于 $i\in[1,n]$ ,$S_{n+i}-S_{i-1}\geq B_i$

  • 对于 $i\in[n+1,2n]$ ,$X-(S_i-S_{i-n-1})\geq B_i$

都能写成差分约束的形式,只需判定是否有负环。

  • $i\rightarrow i-1:0$

  • $2n\rightarrow 0:M$

  • 对于 $i\in[1,n]$ ,$n+i\rightarrow i-1:B_i$

  • 对于 $i\in[n+1,2n]$ ,$i-n-1\rightarrow i:B_i-X$

SPFA 判负环复杂度不太对劲……我们需要一个更加有理有据的方式。

显然这些点两两可达,不妨只考虑 $2n$ 出发的最短路。

观察这张图:

我们将 $2n\rightarrow 0$ 的边断开,再将点 $n$ 删除,那么图就变成两条链,之间有若干边。

此时不存在环,最短路可以 DP 求。求出 $n-1,n+1,0,2n$ 两两的最短路。

然后将点 $n$ 和边 $2n\rightarrow 0$ 加入,只和 $n-1,n+1,0,2n$ 连接,最后对 $5$ 个点的图判负环即可。

复杂度 $O(n\log A)$ 。