题解

思路

根据最大流最小割定理，答案等于把最左列与最右列分开的最小走廊容量和。对每个网格节点只需决定它属于源侧还是汇侧；一条走廊的两端属于不同侧时，它的容量计入割。由于 $n\le5$，可用 $n$ 位二进制数表示一列的分割状态。

做法

子任务 1：枚举全部中间列

第一列必须全在源侧，最后一列必须全在汇侧。枚举其余 $n(m-2)$ 个节点的侧归属，直接累加跨越两侧的水平和竖直走廊容量。

子任务 2：枚举相邻列状态

设 $dp[S]$ 为处理到当前列，该列源侧节点集合为 $S$ 时的最小割。从上一列 $P$ 转移到 $S$ 时，需加上 $P\mathbin{\mathrm{xor}}S$ 中各行对应的水平走廊容量，以及 $S$ 中相邻两位不同的竖直走廊容量。直接枚举 $(P,S)$ 即可。

子任务 3：带权汉明距离变换

一次列转移的水平部分是

$$g[S]=\min_P\left(dp[P]+\sum_{r:P_r\ne S_r}h_r\right).$$

先令 $g=dp$。依次处理每一位 $r$，对不含该位的 $S$，用一次或不使用容量 $h_r$ 的翻转同时更新 $g[S]$ 与 $g[S\cup\{r\}]$。处理完 $n$ 位后，$g$ 就是所有上一列状态的最小值。再为每个 $S$ 加上当前列的环边割代价。

初始只有全 $1$ 状态代价为 $0$，最终答案为最后一列全 $0$ 状态的 DP 值。

复杂度

三层时间复杂度依次为 $O(2^{n(m-2)}nm)$、$O(m4^n n)$ 和 $O(mn2^n)$；满分做法空间复杂度为 $O(2^n)$。

正确性证明

任何一个源汇割都唯一对应于每列的一个位掩码。转移中的带权汉明距离恰好计入相邻列间被割断的走廊，当前列环边代价恰好计入同列被割断的走廊，每条边被计数一次。超立方体变换对每一位选择“保持”或“翻转并付费”，因此结果等于枚举所有 $P$ 的最小值。故 DP 得到所有源汇割的最小容量，由最大流最小割定理即为所求最大流。