题目描述

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

输入输出格式

输入格式:

第 1 行有 2 个正整数 m 和 n,分别表示棋盘的行数和列数。接下来的 m 行,每行有 n 个正整数,表示棋盘方格中的数。

输出格式:

程序运行结束时,将取数的最大总和输出

输入输出样例

输入样例#1:

3 3
1 2 3
3 2 3
2 3 1

输出样例#1:

11

说明

m,n<=100


实际上这个和Exca王者之剑基本上一样..
用那份代码就能A这道题
本来是刷状压dp之后遇到的.
然而数据加强到100状压存不下

其实就是一个黑白染色后跑最小割.
s->黑点 val[i][j]
白点-> val[i][j]
黑点->影响的白点 inf
默认每个点都取,这样跑一遍最大流(既最小割)之后就是答案了

 

分类: 图论题解

说点什么

avatar
  Subscribe  
提醒