#6007. 「网络流 24 题」方格取数
内存限制：256 MiB时间限制：1000 ms标准输入输出
题目类型：传统评测方式：文本比较
上传者： 匿名
题目描述
在一个有 m×n m \times nm×n 个方格的棋盘中，每个方格中有一个正整数。
现要从方格中取数，使任意 2 22 个数所在方格没有公共边，且取出的数的总和最大。试设计一个满足要求的取数算法。
输入格式
文件第 1 11 行有 2 22 个正整数 m mm 和 n nn，分别表示棋盘的行数和列数。接下来的 m mm 行，每行有 n nn 个正整数，表示棋盘方格中的数。
注意：m mm 是行数，n nn 是列数。
输出格式
输出取数的最大总和。
样例
样例输入
3 3
1 2 3
3 2 3
2 3 1样例输出
11数据范围与提示
1≤n,m≤30 1 \leq n, m \leq 301≤n,m≤30
题目链接：https://loj.ac/problem/6007
题意：中文题目，意思明显。
思路：求矩阵的最大点权独立集，这是一个NP问题，但是在二分图中他却等于最小割，用最大流求解。那么这个矩阵明显就是一个二分图啊，把一种一个点涂黑，与黑点相邻的4个点全部涂为白色，与白色相邻的4个点全部涂成黑色，明显不会冲突。
注意：点独立集：不相邻的点的集合 ；点覆盖集：点覆盖全部的边
最大点独立集 + 最小点覆盖集 = |V|
最大点权独立集 + 最小点权覆盖集 = ∑v
在二分图中：最小点覆盖集 = 最大匹配 ；最小点权覆盖集 = 最小割