题解：AT_abc393_g [ABC393G] Unevenness

· · 题解

先写出原问题的线性规划形式：

记 b_{i,j} = a_{i,j} + d_{i,j}，其中 d_{i,j} 是变化量，在线性规划形式中是一个变量。

记 f_{i,j} = |b_{i,j} - b_{i,j+1}|, g_{i,j} = |b_{i,j} - b_{i+1,j}|。

那么我们有：

\begin{aligned} &\min. && \sum f_{i,j} + g_{i,j} \\ &\mathrm{s.t.} && \sum d_{i,j} \le \frac{P}{Q} \\ \end{aligned}

这不是线性规划的标准形式。为了表达 f_{i,j} 和 g_{i,j}，可以这样转化：

然后对于 $\max(b_{i,j} - b_{i,j+1},0)$，可以再引入一个变量 $t_{i,j}$，然后写出限制： $$ b_{i,j} - b_{i,j+1} - t_{i,j} \le 0 $$ 这样 $t_{i,j}$ 的最小值就是我们要求的 $\max$ 了。对于 $f$ 的另一部分和 $g$，也是同样的转化。 于是我们写出来了线性规划形式。官方题解告诉我们这个东西可以对偶成一个费用流问题。不过这题数据范围小，直接跑单纯形也能过，只是会比费用流慢很多。 这题的一个难点是精度要求很严格。不过这题可以用 `__float128` 冲过去，调一调 `eps` 就行。[提交记录](https://atcoder.jp/contests/abc393/submissions/63943194)