#P5403. [2018年湖南省队集训]marshland

    ID: 4415 传统题 1500ms 512MiB 尝试: 235 已通过: 100 难度: 8 上传者: 标签>难度分类提高+/省选-构造与建模奇偶分组图论拆点限制点容量势能优化费用流Dijkstra残量增广路CF2400

[2018年湖南省队集训]marshland

marshland

题目描述

用一个 n×nn\times n 的网格表示沼泽地。第 XX 行第 YY 列的格子记为 (X,Y)(X,Y),左上角为 (1,1)(1,1),右下角为 (n,n)(n,n)。X+YX+Y 为奇数的格子有危险度 VX,YV_{X,Y},其余格子的危险度为 00。

你有 mm 块 L 形石头。每块石头占据同一个 2×22\times2 方块中的三个格子,可以旋转到四种朝向。每块石头只会把它拐角所在格子的危险度变为 00。石头占据的格子不能重叠。

网格上有 kk 条禁止位置记录。石头的任何部分都不能放在禁止位置上。禁止位置的危险度为 00。

可以放置至多 mm 块石头。求放置后所有格子的危险度之和的最小值。

输入格式

第一行三个整数 n,m,kn,m,k。

接下来 nn 行,每行 nn 个整数,表示各格子的危险度。X+YX+Y 为偶数的格子和禁止位置的危险度保证为 00。

接下来 kk 行,每行两个整数 X,YX,Y,表示一个禁止位置。记录可能重复。

输出格式

输出一行一个整数,表示危险度之和的最小值。

样例

3 3 1
0 1 0
2 0 1
0 1 0
1 3
3
3 3 4
0 2 0
0 0 4
0 3 0
1 3
2 1
2 2
3 1
9

补充样例 3

2 1 0
0 7
4 0
4

把一块石头的拐角放在危险度为 77 的格子上,其余两格分别为左侧与下侧的零危险格,剩余危险度为 44。

数据范围

  • 对于 10%10\% 的数据,n≤4n\le4。
  • 对于 30%30\% 的数据,n≤10n\le10。
  • 对于 100%100\% 的数据,n≤50n\le50。

对于所有数据,0≤m≤⌊n2/3⌋0\le m\le\lfloor n^2/3\rfloor,0≤k≤n20\le k\le n^2,0≤VX,Y≤1060\le V_{X,Y}\le10^6。