Description
最近在生物实验室工作的小T遇到了大麻烦。
由于实验室最近升级的缘故，他的分格实验皿是一个长方体,其尺寸为abc，a、b、c 均为正整数。为了实验的方便，它被划分为abc个单位立方体区域，每个单位立方体尺寸为111。用(i,j,k)标识一个单位立方体，1 ≤i≤a，1≤j≤b，1≤k≤c。这个实验皿已经很久没有人用了，现在，小T被导师要求将其中一些单位立方体区域进 行消毒操作（每个区域可以被重复消毒）。而由于严格的实验要求，他被要求使用一种特定 的F试剂来进行消毒。 这种F试剂特别奇怪，每次对尺寸为xyz的长方体区域（它由xyz个单位立方体组 成）进行消毒时，只需要使用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)需要被消毒。输入保证满足abc≤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
3
HINT
对于区域(1,1,3)-(2,2,4)和(1,1,1)-(4,4,1)消毒，分别花费2个单位和1个单位的F试剂。2017.5.26新加两组数据By Leoly，未重测.
Solution
贪心一下，每次消毒肯定是消一个面嘛，\(x*y*1\) ，耗费只要 \(1\)
\(a*b*c \leq 5000\) ，所以 \(min\{a,b,c\} \leq 17\)
那么用 \(2^{min\{a,b,c\}}\) 时间枚举最小维度上消除了哪些面，那么剩下的就只能用剩下两个维度的面去消除
我们可以把剩下的拍扁成一个二维平面，那么两个维度的面在平面内就变成了一行和一列。于是就变成了二位平面覆盖问题，每次选定一行或一列，这一行或一列上的所有点全部完成，询问把所有给出点完成需要选择的最少次数
把二位平面上需要完成的点的横纵坐标连一条边，于是就变成了最小点覆盖，由于是二分图，跑最大匹配即可
有趣的一些事情：
我用网络流怎么都跑不快，一用匈牙利，快了 \(30\) 倍。。。 \(30\) ！
然后这题BZOJ是真的卡常，最后各种操作， \(9.7s\) 过了（时限 \(10s\) ）
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=5000+10,inf=0x3f3f3f3f;
int e,to[MAXN<<1],nex[MAXN<<1],beg[MAXN<<1],use[MAXN],connect[MAXN];
struct node{
int x,y,z;
};
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!='\0')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void insert(int x,int y)
{
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
}
inline bool dfs(int x)
{
for(register int i=beg[x];i;i=nex[i])
if(!use[to[i]])
{
use[to[i]]=1;
if(!connect[to[i]]||dfs(connect[to[i]]))
{
connect[to[i]]=x;
return true;
}
}
return false;
}
int main()
{
static node point[MAXN];
static int T,a,b,c,ans=inf,cnt,now,n,m,pop[140000];
read(T);
while(T--)
{
ans=inf;cnt=0;
read(a);read(b);read(c);
for(register int i=1;i<=a;++i)
for(register int j=1;j<=b;++j)
for(register int k=1;k<=c;++k)
{
static int x;read(x);
if(!x)continue;
point[++cnt]=(node){i,j,k};
}
if(b<a)
{
std::swap(a,b);
for(register int i=1;i<=cnt;++i)std::swap(point[i].x,point[i].y);
}
if(c<a)
{
std::swap(a,c);
for(register int i=1;i<=cnt;++i)std::swap(point[i].x,point[i].z);
}
n=b,m=c;
for(register int st=0;st<(1<<a);++st)pop[st]=__builtin_popcount(st);
for(register int st=0;st<(1<<a);++st)
{
e=0;
for(register int i=1;i<=cnt;++i)
if(!(st&(1<<point[i].x-1)))insert(point[i].y,point[i].z);
now=0;
for(register int i=1;i<=n;++i)
{
for(register int j=1;j<=m;++j)use[j]=0;
if(dfs(i))now++;
if(now+pop[st]>=ans)break;
}
chkmin(ans,pop[st]+now);
for(register int i=1;i<=n;++i)beg[i]=0;
for(register int i=1;i<=m;++i)connect[i]=0;
}
write(ans,'\n');
}
return 0;
}