问题分析

在一个 $m \times n$ 的网格中：

• 每个格子有一个正整数权值
• 要求选出一部分格子，使得任意两个被选格子没有公共边
• 目标是最大化所选格子的权值和

这等价于在网格图中找一个最大权独立集。

---

关键观察

网格是一个二分图：

• 将棋盘按 $(i+j) \bmod 2$ 染色（类似国际象棋棋盘的黑白染色）
• 任意两个相邻的格子颜色不同
• 每条边连接一个黑格和一个白格

设：

• 黑格集合为 $B$
• 白格集合为 $W$

---

网络流建模

这是一个二分图最大点权独立集问题，可以转化为最小割：

最大权独立集 = 总权值和 − 最小点权覆盖

而二分图中，最小点权覆盖可以通过网络流求解：

建图方法：

1. 源点 $S$ 向每个黑格 $(i,j)$ 连边，容量 = 该格权值
2. 每个白格 $(i,j)$ 向汇点 $T$ 连边，容量 = 该格权值
3. 每个黑格向它的相邻白格（上下左右）连边，容量 = $+\infty$

---

算法正确性解释

• 最小割会将图中的点分成两部分：与 $S$ 连通的，和与 $T$ 连通的
• 由于黑格到白格的边容量为无穷大，它们不会被割掉
• 因此最小割只能割 $S$→黑格 或 白格→$T$ 的边
• 割掉 $S$→黑格 的边表示不选这个黑格
• 割掉 白格→$T$ 的边表示选这个白格

最小割的值 = 放弃的格子权值和（即最小点权覆盖的权值和）

所以： [ \text{最大权独立集} = \text{总权值和} - \text{最小割} ]

---

样例验证

输入：

3 3
1 2 3
3 2 3
2 3 1

棋盘：

(1,1)=1  (1,2)=2  (1,3)=3
(2,1)=3  (2,2)=2  (2,3)=3  
(3,1)=2  (3,2)=3  (3,3)=1

按 $(i+j) \bmod 2$ 染色：

• 黑格：$(1,1), (1,3), (2,2), (3,1), (3,3)$
• 白格：$(1,2), (2,1), (2,3), (3,2)$

建图：

• $S$ → 黑格：容量分别为 1, 3, 2, 2, 1
• 白格 → $T$：容量分别为 2, 3, 3, 3
• 黑格与相邻白格连无穷大边

计算：

• 总权值和 = $1+2+3+3+2+3+2+3+1 = 20$
• 最小割 = 9
• 最大权独立集 = $20 - 9 = 11$

输出：11

验证：一种最优解是选 $(1,2)=2, (1,3)=3, (2,1)=3, (3,2)=3$，总和 $2+3+3+3=11$，且它们互不相邻。

---

算法步骤

1. 读入 $m, n$ 和棋盘权值
2. 计算总权值和
3. 建图：
   • 节点：$S$（0）, 每个格子编号 $(i-1)*n+j$，$T$（$m*n+1$）
   • 对每个格子 $(i,j)$：
     • 如果是黑格：$S$ → 格子，容量 = 权值
     • 如果是白格：格子 → $T$，容量 = 权值
   • 对每个黑格，向相邻的白格连边，容量 = $+\infty$
4. 计算 $S$ 到 $T$ 的最大流（最小割）
5. 输出：总权值和 − 最大流

---

复杂度分析

• 节点数：$m \times n + 2 \leq 902$
• 边数：每个格子最多4个邻居，$O(4mn)$
• 使用 Dinic 算法：$O(V^2E) = O((mn)^2 \cdot mn)$
• 在 $m,n \leq 30$ 时完全可行

---

总结

这道题通过棋盘二分图染色，将最大权独立集问题转化为最小割问题，利用网络流高效求解，是处理网格图约束选取问题的经典方法。