题目描述
最近在生物实验室工作的小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试剂。
Solution
有一个较为明显的贪心策略：每次消毒令x，y，z中一个为 1 ，其他为最大值
三分图匹配不会（可能是我太蒻了），发现a，b，c中一定有一个 <= 50001/3 ~=17.1，217复杂度还可以接受。
于是可以旋转长方体，使 a，b，c 中最小的一个为长方形的高，不妨设它为a。
设同一高度的所有单位立方体为一层，枚举每一层是对这一层全部消毒还是留下
留下来的压缩到一个平面上，然后就是二维的问题了。
题外话：
除二分图匹配的 “ 0 要素 ” 和 “ 1 要素 ”外，最小点覆盖还有一个 “ 2 要素”：
每条边有 2 个端点，二者至少选择一个
将平面上每个需要消毒的单位正方形的所在行数和列数连边，求最小点覆盖
Code
#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> using namespace std; const int N=5e3+10; int match[N],head[N],nxt[N],tot,ver[N]; int T,a,b,c,n,ans,pos,s[3][N],cnt,vis[N]; bool flag[N]; void add(int x,int y) { ver[++tot]=y,nxt[tot]=head[x],head[x]=tot; } bool dfs(int x) { for(int i=head[x],y;i;i=nxt[i]) if(vis[y=ver[i]]!=cnt) { vis[y]=cnt; if(!match[y] || dfs(match[y])) { match[y]=x; return 1; } } return 0; } void clear() { tot=0; memset(head,0,sizeof(head)); memset(match,0,sizeof(match)); } int solve(int x) { clear(); int now=0; for(int i=0;i<a;i++) if(x&(1<<i)) flag[i+1]=false,now++; else flag[i+1]=true; for(int i=1;i<=n;i++) if(flag[s[0][i]]) add(s[1][i],s[2][i]); for(int i=1;i<=b;i++) { cnt++; if(dfs(i)) now++; } return now; } int main() { scanf("%d",&T); while(T--) { n=cnt=0,ans=1<<30; memset(vis,0,sizeof(vis)); scanf("%d%d%d",&a,&b,&c); for(int i=1;i<=a;i++) for(int j=1;j<=b;j++) for(int k=1;k<=c;k++) { scanf("%d",&pos); if(!pos) continue; s[0][++n]=i,s[1][n]=j,s[2][n]=k; } int mi=min(a,min(c,b)); if(mi==b) swap(a,b),swap(s[0],s[1]); if(mi==c) swap(a,c),swap(s[0],s[2]); for(int i=0;i<(1<<a);i++) ans=min(ans,solve(i)); printf("%d\n",ans); } return 0; }
原文：https://www.cnblogs.com/hsez-cyx/p/12348658.html