100 #P3140. [HNOI2013] 消毒

    ID: 2295 传统题 4000ms 128MiB 尝试: 2242 已通过: 540 难度: 7 上传者: 标签>难度分类提高+/省选-枚举与搜索枚举较小维度全子集枚举图论二分图建模顶点覆盖Hopcroft–KarpCF2200

[HNOI2013] 消毒

[HNOI2013] 消毒

题目描述

生物实验室里,小 T 有一个尺寸为 a×b×ca\times b\times c 的长方体实验皿。实验皿被分为 abcabc 个单位立方体,分别用 (i,j,k)(i,j,k) 表示,其中 1≤i≤a1\le i\le a、1≤j≤b1\le j\le b、1≤k≤c1\le k\le c。导师要求小 T 给其中指定的单位立方体消毒。

每次操作可以选一个由连续的单位立方体组成、各边沿实验皿坐标轴的长方体区域。若该区域的尺寸为 x×y×zx\times y\times z,消毒要用 min⁡(x,y,z)\min(x,y,z) 单位的 F 试剂。可以给同一个单位立方体消毒多次,也可以覆盖无需消毒的单位立方体。

求覆盖所有指定的单位立方体最少要用多少单位的 F 试剂。

输入格式

第一行是一个正整数 DD,表示数据组数。

每组数据的第一行是三个正整数 a,b,ca,b,c,表示实验皿的尺寸。

接下来依次给出 aa 个矩阵,每个矩阵有 bb 行 cc 列,元素用空格分隔。第 ii 个矩阵的第 jj 行第 kk 列为 11,表示 (i,j,k)(i,j,k) 需要消毒,为 00 则表示无需消毒。

输出格式

对每组数据输出一行一个整数,表示最少需要的 F 试剂用量。

样例

1
4 4 4
1 0 1 1
0 0 1 1
0 0 0 0
0 0 0 0
0 0 1 1
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0
3

从 (1,1,3)(1,1,3) 到 (2,2,4)(2,2,4) 的长方体需要 22 单位试剂,从 (1,1,1)(1,1,1) 到 (4,4,1)(4,4,1) 的长方体需要 11 单位试剂。两次消毒覆盖了所有指定的单位立方体。

数据范围

1≤D≤31\le D\le 3,a,b,ca,b,c 均为正整数,且 abc≤5000abc\le 5000。