警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「HNOI 2013」切糕 - 最小割

题意

传送门:洛谷 P3227 - 切糕

给你一个空矩阵 \(a\),你要填上 \(n\) 行,每行 \(m\) 个数,求满足:

\(\forall (i, j) ~\text{以及相邻的坐标}~ (x, y), |a_{i,j} - a_{x,y}| \le d\) 时, \(\sum v_{i,j,a_{i,j}}\) 的最大值。

\(1 \le a_{i,j}, d_{i,j} \le k\)\(n, m, k \le 40\)

解法

考虑对每个变量开 \(k\) 个点,点 \((x, y, z)\) 代表点 \((x, y)\) 取值 \(z\)

我们规定割掉 \((x, y, z-1) \to (x, y, z)\) 的边代表变量 \((x, y)\)\(z\)

那么对于 \(1 < z \le k\)\((x, y, z-1) \xrightarrow{v_{x,y,z}} (x, y, z)\)

但是怎么加上 \(d\) 的限制呢?

注意到 \(|x - y| \le z\) 等价于 \(x - y \le z\)\(y - x \le z\)。对于每一条不等式限制,我们可以这么连边:

显然,\(+\infty\) 的边是割不掉的。那么如果我割掉了 \((1, 1, x-1) \to (1, 1, x)\)\((1, 2, y-1) \to (1, 2, y)\) 的边,那么显然是有 \(x - 2 \le y\) 的。

所以对于每一个点 \((x, y, z)\),往四连通的 \((u, v, z - d)\) 连一条容量为 \(+\infty\) 的边。

代码