巧克力选择问题题解

题目分析

题目要求在 $n \times m$ 的巧克力网格中，选出连通且包含至少 $k$ 种图案（$1 \le k \le 5$）的子集，满足两个优化目标：

1. 子集的块数尽可能少；
2. 块数最少时，美味值的中位数（第 $\lfloor \frac{n+1}{2} \rfloor$ 小的数）尽可能小。 其中，$c_{i,j}=-1$ 的巧克力不可选，最终需输出最优解或 $-1\ -1$（无解）。

关键难点

• 需同时满足“连通性”“至少 $k$ 种图案”“最小块数”“最小中位数”四重约束；
• $k \le 5$ 是关键条件，可通过状态压缩（状压DP）处理图案种类的约束；
• 中位数的最小化需结合二分查找与代价建模。

核心思路

1. 问题拆解与优化顺序

• 第一步：找到满足条件的最小块数 $O$；
• 第二步：在块数为 $O$ 的前提下，找到最小中位数。

2. 状压DP + 最短路：求解最小块数

• 状态定义：$f[s][u]$ 表示以位置 $u$ 为终点，包含的图案种类为状态 $s$（二进制掩码，$s$ 的第 $i$ 位为 1 表示包含第 $i$ 种图案）的最小块数；
• 初始化：对每个可选位置 $u$，若其图案为 $c$，则 $f[1 \ll p[c]][u] = 1$（$p[c]$ 为图案 $c$ 映射的 0~k-1 编号，代码中通过随机映射优化）；
• 状态转移：
  1. 子集合并：对状态 $s$，枚举其子集 $t$，合并 $t$ 和 $s \oplus t$ 的状态，更新 $f[s][u] = \min(f[s][u], f[t][u] + f[s \oplus t][u] - 1)$（减 1 是因为位置 $u$ 被重复计算）；
  2. 连通性扩展：将网格抽象为图（相邻可选位置连边，边权为 1），用 SPFA 算法松弛状态，保证连通性；
• 结果提取：$O = \min(f[(1<<k)-1][u])$（$(1<<k)-1$ 表示包含所有 $k$ 种图案）。

3. 二分 + 代价重构：求解最小中位数

• 离散化：将所有美味值离散化，便于二分查找；
• 二分中位数：假设当前二分的中位数为 $mid$，重构代价函数：
  • 若位置 $u$ 的美味值 $\le mid$，则代价 $w[u] = 255$（小权重，代表“更优”）；
  • 否则 $w[u] = 257$（大权重）；
• 代价建模：将块数约束（$O$）转化为代价约束 $res \le O \times 256$（256 为权重基数，保证块数优先），若满足则说明当前 $mid$ 可行，尝试更小值。

4. 随机映射优化

代码中通过随机映射 $p[c]$ 将图案 $c$ 映射到 0~k-1 编号，多次随机运行以避免局部最优，提升结果准确性。

解题步骤

1. 预处理

• 读取输入，记录每个位置的图案 $c_{i,j}$ 和美味值 $a_{i,j}$；
• 对美味值离散化，为后续二分做准备。

2. 求解最小块数

• 多次随机映射图案编号，运行 work() 函数：
  • 初始化状压DP数组 $f$；
  • 构建网格图，通过子集合并 + SPFA 松弛状态；
  • 提取最小块数 $O$。

3. 求解最小中位数

• 二分离散化后的美味值，对每个 $mid$：
  • 重构代价函数 $w[u]$；
  • 重新运行状压DP + SPFA，验证是否存在块数为 $O$ 且中位数 $\le mid$ 的方案；
  • 调整二分边界，找到最小可行中位数。

4. 结果输出

• 若存在可行解，输出最小块数 $O$ 和对应的最小中位数；否则输出 $-1\ -1$。

复杂度分析

• 状态数：$2^k \times (n \times m)$，$k \le 5$ 时 $2^5=32$，$n \times m \le 233$，状态数约 $32 \times 233 = 7456$；
• SPFA 复杂度：每次 SPFA 为 $O(E)$（$E$ 为边数，约 $4 \times n \times m$）；
• 二分次数：离散化后约 $O(\log(10^6)) \approx 20$；
• 随机运行次数：代码中运行 120 次，整体复杂度可接受。

总结

本题的核心是状压DP + 最短路结合二分查找的综合应用：

1. 利用 $k \le 5$ 的条件，通过状压DP处理图案种类约束，结合SPFA保证连通性，求解最小块数；
2. 通过二分中位数 + 代价重构，将中位数最小化问题转化为代价约束的验证问题；
3. 随机映射图案编号是代码的优化技巧，避免因固定映射导致的局部最优。

这种“先求核心约束（最小块数），再优化次要目标（最小中位数）”的思路，以及“状压 + 图论”的组合模型，是解决多约束优化问题的典型方法。同时，随机化的引入也体现了对非确定性问题的工程优化思路。