bzoj3140: [Hnoi2013]消毒

Description

最近在生物实验室工作的小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中的最小者。)

Input

第一行是一个正整数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。

Output

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

Sample Input

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

Sample Output

HINT

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

题解：

显然选择的区域有一维要是1，其他维要最大

题目就相当于问最少切多少个面才能覆盖所有点

二维的很简单，直接二分图匹配即可

可是这是三维的，可没有什么三分图匹配

但我们注意到，a，b，c中的最小值至多为17

我们就可以2¹⁷枚举最小的那维切不切，剩下的就变成二位的了

注意常数

code：

 1 #include<cstdio>
 2 #include<iostream>
 3 #include<cmath>
 4 #include<cstring>
 5 #include<algorithm>
 6 #define maxn 5005
 7 using namespace std;
 8 char ch;
 9 bool ok;
10 void read(int &x){
11     for (ok=0,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=1;
12     for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());
13     if (ok) x=-x;
14 }
15 int T,a,b,c,x,cnt,ans;
16 struct Point{int x,y,z;}point[maxn];
17 int tot,idx,now[maxn],son[maxn],pre[maxn],match[maxn],vis[maxn];
18 void put(int a,int b){pre[++tot]=now[a],now[a]=tot,son[tot]=b;}
19 bool dfs(int u){
20     for (int p=now[u],v=son[p];p;p=pre[p],v=son[p])
21         if (vis[v]!=idx){
22             vis[v]=idx;
23             if (!match[v]||dfs(match[v])){match[v]=u;return true;}
24         }
25     return false;
26 }
27 int work(int sta){
28     for (int i=1;i<=a;i++) now[i]=0;
29     for (int i=1;i<=a;i++) match[i]=0;
30     tot=0;
31     for (int i=1;i<=cnt;i++) if (sta&(1<<(point[i].z-1))) put(point[i].x,point[i].y);
32     int ans=0;
33     for (;sta;sta>>=1) if (sta&1) ans++;
34     ans=c-ans;
35     for (int i=1;i<=a;i++){
36         ++idx;
37         if (dfs(i)) ans++;
38     }
39     return ans;
40 }
41 int main(){
42     for (read(T);T;T--){
43         read(a),read(b),read(c),cnt=0;
44         for (int i=1;i<=a;i++)
45             for (int j=1;j<=b;j++)
46                 for (int k=1;k<=c;k++){
47                     read(x);
48                     if (x) point[++cnt]=(Point){i,j,k};
49                 }
50         if (a<b&&a<c){
51             swap(a,c);
52             for (int i=1;i<=cnt;i++) swap(point[i].x,point[i].z);
53         }
54         else if (b<a&&b<c){
55             swap(b,c);
56             for (int i=1;i<=cnt;i++) swap(point[i].y,point[i].z);
57         }
58         ans=c;
59         for (int sta=0;sta<(1<<c);sta++) ans=min(ans,work(sta));
60         printf("%d
",ans);
61     }
62     return 0;
63 }