[图论记录]ARC117F Gateau

**题意** ： 有一个长为 $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)$ 。 ```cpp ```