题目描述
最近在生物实验室工作的小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 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)-(2,2,4)和(1,1,1)-(4,4,1)消毒，分别花费2个单位和1个单位的F试剂。
题解
我们先来考虑一下二维的情况
对于一整块需要染色的部分，我们可以选择一条一条地去染色（也就是说使每一次的最小值为$1$，另一个就可以随便取了），那么答案肯定不会比直接一块染更差
比方说$(1,1)$到$(2,3)$都有，你直接整块染或者每次染一行实际上答案是一样的
所以我们对每一个点的$x->y$连一条边，然后要求一个最小点覆盖，等于最大匹配
然后怎么考虑三维的情况？我们可不会三分图，那个可没有多项式解法
考虑到$a,b,c$中最小的不会超过17（因为$17^3=4913$），所以我们可以考虑枚举这一维，枚举每一层是否直接切掉
剩下没有切的层已经是一个二维的情况了，可以直接用二分图跑
ps：我抄借鉴代码的时候有很多细节问题不明白，比如二分图为什么可以不用拆成左右两边的点，可以在一排点里直接连。后来发现是因为右边的点有用的只有它与哪个左部点匹配，所以只需要一排点也可以记录这些信息（因为我二分图根本没学过所以理解起来很吃力……以前都是直接用网络流跑的从来没去了解过匈牙利……）
1 //minamoto 2 #include<iostream> 3 #include<cstdio> 4 #include<cstring> 5 #include<queue> 6 #define inf 0x3f3f3f3f 7 using namespace std; 8 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) 9 char buf[1<<21],*p1=buf,*p2=buf; 10 template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;} 11 inline int read(){ 12 #define num ch-'0' 13 char ch;bool flag=0;int res; 14 while(!isdigit(ch=getc())) 15 (ch=='-')&&(flag=true); 16 for(res=num;isdigit(ch=getc());res=res*10+num); 17 (flag)&&(res=-res); 18 #undef num 19 return res; 20 } 21 const int N=5005; 22 int head[N],Next[N],ver[N],edge[N],Pre[N],vis[N],tot; 23 int sx[4][N],a,b,c,ans,st[N],num,mn; 24 inline void add(int u,int v){ 25 ver[++tot]=v,Next[tot]=head[u],head[u]=tot; 26 } 27 bool dfs(int u){ 28 for(int i=head[u];i;i=Next[i]){ 29 int v=ver[i]; 30 if(!vis[v]){ 31 vis[v]=true; 32 if(!Pre[v]||dfs(Pre[v])){ 33 Pre[v]=u;return true; 34 } 35 } 36 } 37 return false; 38 } 39 void work(int x){ 40 memset(head,0,sizeof(head)); 41 memset(Pre,0,sizeof(Pre)); 42 tot=0; 43 int tmp=0; 44 for(int i=0;i<a;++i){ 45 if(x&(1<<i)) st[i+1]=false,++tmp; 46 else st[i+1]=true; 47 } 48 for(int i=1;i<=num;++i) 49 if(st[sx[1][i]]) add(sx[2][i],sx[3][i]); 50 for(int i=1;i<=b;++i){ 51 for(int j=1;j<=c;++j) vis[j]=false; 52 if(dfs(i)) ++tmp; 53 } 54 cmin(ans,tmp); 55 } 56 int main(){ 57 int T=read(); 58 while(T--){ 59 num=0,ans=inf; 60 a=read(),b=read(),c=read(); 61 mn=min(a,min(b,c)); 62 for(int i=1;i<=a;++i) 63 for(int j=1;j<=b;++j) 64 for(int k=1;k<=c;++k){ 65 int u=read(); 66 if(!u) continue; 67 sx[1][++num]=i; 68 sx[2][num]=j; 69 sx[3][num]=k; 70 } 71 if(mn==b) swap(a,b),swap(sx[1],sx[2]); 72 else if(mn==c) swap(a,c),swap(sx[1],sx[3]); 73 for(int i=0;i<(1<<a);++i) work(i); 74 printf("%d ",ans); 75 } 76 return 0; 77 }