P3231 [HNOI2013]消毒

    • 434通过
    • 881提交
  • 题目提供者 洛谷OnlineJudge
  • 评测方式 云端评测
  • 标签 二分图 搜索 枚举,暴力 2013 湖南 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    最近在生物实验室工作的小T遇到了大麻烦。 由于实验室最近升级的缘故,他的分格实验皿是一个长方体,其尺寸为a*b*c,a、b、c 均为正整数。为了实验的方便,它被划分为a*b*c个单位立方体区域,每个单位立方体尺寸为1*1*1。用(i,j,k)标识一个单位立方体,1 <=i<=a,1<=j<=b,1<=k<=c。这个实验皿已经很久没有人用了,现在,小T被导师要求将其中一些单位立方体区域进 行消毒操作(每个区域可以被重复消毒)。

    而由于严格的实验要求,他被要求使用一种特定 的F试剂来进行消毒。 这种F试剂特别奇怪,每次对尺寸为x*y*z的长方体区域(它由x*y*z个单位立方体组 成)进行消毒时,只需要使用min{x,y,z}单位的F试剂。F试剂的价格不菲,这可难倒了小 T。

    现在请你告诉他,最少要用多少单位的F试剂。(注:min{x,y,z}表示x、y、z中的最小 者。)

    输入输出格式

    输入格式:

    第一行是一个正整数D,表示数据组数。接下来是D组数据,每组数据开头是三个数a,b,c表示实验皿的尺寸。接下来会出现a个b 行c列的用空格隔开的01矩阵,0表示对应的单位立方体不要求消毒,1表示对应的单位立方体需要消毒;例如,如果第1个01矩阵的第2行第3列为1,则表示单位立方体(1,2,3)需要被消毒。输入保证满足a*b*c<=5000,T<=3。

    输出格式:

    仅包含D行,每行一个整数,表示对应实验皿最少要用多少单位 的F试剂。

    输入输出样例

    输入样例#1: 复制
    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
    输出样例#1: 复制
    3

    说明

    对于区域(1,1,3)-(2,2,4)和(1,1,1)-(4,4,1)消毒,分别花费2个单位和1个单位的F试剂。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。