

$9.$方格取数问题

题目

在一个有 $m\times n$ 个方格的棋盘中，每个方格中有一个正整数。现要从方格中取数，使任意 $2$ 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘，按照取数要求编程找出总和最大的数。

题解

这个可能方格图问题的某种解决套路吧，就是按照坐标黑白染色，建出二分图。 首先按照坐标之和为奇或偶进行黑白染色，将同种类型的放到一个集合中，然后会形成两个集合 $X, Y$，由 $S$ 点向 $X$ 集合中的点连容量为原图中权值的边， $Y$ 集合向 $T$ 类似的连边，由于不能同时选有相邻边的点，那么 $X$ 集合中的点向 $Y$ 集合中的与其有相邻边的点连边为 $inf$，根据建图方法肯定会是有相邻边的两点不在同一集合中。 此时跑出最大流，用所有格子的权值和减去最大流就是结果。

正确性

因为这样跑出来的最大流就是二分图的最小割，又由于中间的连边容量为无限大，所以肯定不会被割到，那么对一个格子（设它在二分图中属于 $X$ 集合），要么将他与 $S$ 之间的边割掉（这就相当于在原图中没有取这个格子），要么将其连向 $Y$ 中的所有点之间的连边割掉（这就相当于在原图中取了这个格子但是美取相邻的），由于是最小割，而且过程完全满足题中规定的条件，所以最小割就是不取的格子最小权值和。