首页 > 代码库 > LiberOJ #6007. 「网络流 24 题」方格取数 最小割 最大点权独立集 最大流
LiberOJ #6007. 「网络流 24 题」方格取数 最小割 最大点权独立集 最大流
#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 31 2 33 2 32 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
在二分图中：最小点覆盖集 = 最大匹配 ；最小点权覆盖集 = 最小割
LiberOJ #6007. 「网络流 24 题」方格取数 最小割 最大点权独立集 最大流
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。