#P1475. 方格取数

    ID: 487 传统题 1000ms 512MiB 尝试: 1236 已通过: 463 难度: 6 上传者: 标签>CF2100提高最大权独立集补集转化二分图建模顶点覆盖最小割建模最大流最小割定理Dinic当前弧优化

方格取数

题目描述

在一个 n×nn \times n 的方格里,每个格子里都有一个正整数。从中取出若干数,使得任意两个取出的数所在格子没有公共边,且取出的数的总和尽量大。

输入格式

第一行一个数 n (n≤30)n~(n \leq 30)

接下来 nn 行每行 nn 个数描述一个方阵。

输出格式

仅一个数,即最大和。

2
1 2
3 5
6

本站数据版本约定

格子中的数均不超过 10910^9。