题目名称	1842. [国家集训队2011]圈地计划
输入输出	`nt2011_land.in/out`
难度等级	★★★☆
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	20
题目来源	cstdio 于2014-12-05加入
开放分组	全部用户
提交状态
分类标签	网络流
	分享题解

通过：48，提交：72，通过率：66.67%
Youngsc	100	0.000 s	0.00 MiB	C++
L_in	100	0.005 s	0.75 MiB	C++
AAAAAAAAAA	100	0.005 s	1.75 MiB	C++
Qw	100	0.005 s	1.79 MiB	C++
_Itachi	100	0.005 s	1.92 MiB	C++
kito	100	0.005 s	4.62 MiB	C++
YPZ_979	100	0.005 s	5.03 MiB	C++
test	100	0.005 s	6.28 MiB	C++
test	100	0.005 s	6.28 MiB	C++
test	100	0.005 s	6.28 MiB	C++

关于圈地计划的近10条评论(全部评论)
1A AAAAAAAAAA 2017-08-07 12:08 4楼
恩 YPZ_979 2017-07-24 15:01 3楼
翻转源汇大法軣！ _Itachi 2017-01-11 06:08 2楼
强行让工业区和商业区相邻也是醉了…… cstdio 2014-12-05 15:55 1楼

1842. [国家集训队2011]圈地计划

★★★☆ 输入文件：nt2011_land.in 输出文件：nt2011_land.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

最近房地产商GDOI(Group of Dumbbells Or Idiots)从NOI(Nuts Old Idiots)手中得到了一块开发土地。据了解，这块土地是一块矩形的区域，可以纵横划分为N×M块小区域。GDOI要求将这些区域分为商业区和工业区来开发。根据不同的地形环境，每块小区域建造商业区和工业区能取得不同的经济价值。更具体点，对于第i行第j列的区域，建造商业区将得到Aij收益，建造工业区将得到Bij收益。另外不同的区域连在一起可以得到额外的收益，即如果区域(i,j)相邻（相邻是指两个格子有公共边）有k块（显然k不超过4）类型不同于(i,j)的区域，则这块区域能增加k×Cij收益。经过Tiger.S教授的勘察，收益矩阵A,B,C都已经知道了。你能帮GDOI求出一个收益最大的方案么？

【输入格式】

输入第一行为两个整数，分别为正整数N和M，分别表示区域的行数和列数；

第2到N+1列，每行M个整数，表示商业区收益矩阵A；

第N+2到2N+1列，每行M个整数，表示工业区收益矩阵B；

第2N+2到3N+1行，每行M个整数，表示相邻额外收益矩阵C。

【输出格式】

输出只有一行，包含一个整数，为最大收益值。

【样例输入】

3 3

1 2 3

4 5 6

7 8 9

9 8 7

6 5 4

3 2 1

1 1 1

1 3 1

1 1 1

【样例输出】

【提示】

N, M ≤ 100; 0 ≤ Aij, Bij, Cij ≤ 1000

对于30%的数据有N, M ≤ 6

对于50%的数据有N, M ≤ 20

对于100%的数据有N, M ≤ 100

【来源】

国家集训队2011 李其乐