#P2774. 方格取数问题

    ID: 5079 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>网络流O2优化深度优先搜索,DFS最大流最小割网络流 24 题

方格取数问题

题目描述

有一个 mmnn 列的方格图,每个方格中都有一个正整数。现要从方格中取数,使任意两个数所在方格没有公共边,且取出的数的总和最大,请求出最大的和。

输入格式

第一行是两个用空格隔开的整数,分别代表方格图的行数 mm 和列数 nn

22 到第 (m+1)(m + 1) 行,每行 nn 个整数,第 (i+1)(i + 1) 行的第 jj 个整数代表方格图第 ii 行第 jj 列的的方格中的数字 ai,ja_{i, j}

输出格式

输出一行一个整数,代表和最大是多少。

3 3
1 2 3
3 2 3
2 3 1 
11

提示

数据规模与约定

对于 100%100\% 的数据,保证 1n,m1001 \leq n, m \leq 1001ai,j1051 \leq a_{i, j} \leq 10^5

提示

请注意输入的第一行先读入 mm 再读入 nn