题解分析

问题本质

这是一个带颜色约束的矩形铺砖优化问题。我们需要：

1. 将给定的N块瓷砖铺满H×W的网格
2. 瓷砖有1×1和1×2两种（可旋转）
3. 每块瓷砖有固定颜色
4. 优化目标：最大化相邻格子之间颜色对的收益总和

核心难点

1. 双重约束：既要满足瓷砖尺寸布局，又要满足颜色数量限制
2. 收益计算：收益基于相邻格子颜色，是二次目标函数
3. 配对要求：1×2瓷砖的两个格子必须相邻且同色

标准解法思路（网络流建模）

1. 基本观察

• 将网格黑白染色（国际象棋棋盘）
• 1×2瓷砖必然覆盖一黑一白两个相邻格子
• 这暗示了匹配结构：黑格和白格之间的配对

2. 问题分解

将原问题分解为两个相互关联的子问题：

• 颜色分配：决定每个格子的颜色
• 瓷砖布局：决定哪些相邻格子组成1×2瓷砖

3. 网络流模型框架

节点设计：

• 源点S，汇点T
• 颜色节点Col_c（1≤c≤K）
• 格子节点Cell_{r,c}
• 配对节点Pair_c（用于处理1×2瓷砖）
• 边节点Edge_{u,v}（用于计算相邻收益）

关键约束的实现：

(1) 颜色数量约束

• S → Col_c：容量 = cnt1[c] + 2×cnt2[c]（颜色c需要的总格子数）
• 保证颜色c恰好覆盖这么多格子

(2) 格子颜色分配

• Col_c → Cell_{r,c}：容量=1，费用=0
• 每个格子只能从一种颜色获得流量

(3) 相邻边收益处理

• 这是最巧妙的部分：将二次收益线性化
• 对于相邻格子(u,v)，建立中间节点E
• 从u和v到E各有一条边，容量为1
• 从E到T的边带有费用，反映颜色组合的收益
• 通过流量选择来模拟"如果u颜色=j，v颜色=k，则收益A_{j,k}"

(4) 1×2瓷砖配对约束

• 额外流量：从颜色节点Col_c到配对节点Pair_c，容量=cnt2[c]
• 再从Pair_c连接到可能配对的相邻格子对
• 当流量通过配对路径时，强制这两个格子同色且相邻

4. 收益计算的转化技巧

目标函数：∑_{(u,v)相邻} A[color(u)][color(v)]

转化为网络流中的费用：

• 先假设所有相邻边都获得"基准收益"
• 如果两个格子配对（属于同一块1×2瓷砖），则：
  • 它们之间的边收益从A[c1][c2]变为A[c][c]（c1=c2=c）
  • 这个变化量可以作为配对流的"奖励"
• 如果两个格子不配对但相邻，维持原收益计算

5. 求解与恢复

求解：

• 构建上述网络流图
• 求最小费用最大流（将最大化收益转化为最小化负收益）
• 必须流满所有格子节点（铺满整个网格）

方案恢复：

1. 从颜色节点到格子节点的流量确定每个格子的颜色
2. 从配对节点的流量确定哪些相邻格子组成了1×2瓷砖
3. 剩余的单个格子对应1×1瓷砖
4. 按照输入顺序分配具体的瓷砖编号

算法复杂度

• 节点数：O(HW + K)
• 边数：O(HW)（每个相邻关系对应若干边）
• 对于H,W≤100的情况是可解的

实践建议

1. 简化起手：先忽略颜色，只解决铺砖问题（简单的二分图匹配）
2. 逐步增加约束：先固定颜色分配，再解决配对；或先固定配对，再优化颜色
3. 启发式改进：在得到可行解后，可以尝试局部交换优化
4. 注意对称性：A_{j,k}=A_{k,j}可以减少一半的边

本题启示

这类"铺砖+颜色优化"问题在竞赛中常见，核心思想是：

• 通过巧妙的图建模将组合约束转化为流量约束
• 将非线性目标通过附加节点线性化
• 利用匹配结构（二分图）处理尺寸约束

理解这个建模范式，可以解决许多类似的组合优化问题。即使在实际比赛中无法实现完整网络流，基于这个思路设计的贪心或局部搜索算法也能获得不错的分数。