题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3140
如果这是一个二维的图，那么二分图最小覆盖就可以了。然后题目是一个三维的，所以2^h枚举砍掉的层数，然后对于没有砍掉的层，全部压到一张图上跑二分图最小覆盖就可以了。
注意令z轴最短，这样它最多也只有17。 其次不要作死memset，还是老老实实for一遍去初始化。。
#include<cstring> #include<cstdio> #include<algorithm> #include<cmath> #include<iostream> #define rep(i,l,r) for (int i=l;i<=r;i++) #define down(i,l,r) for (int i=l;i>=r;i--) #define clr(x,y) memset(x,y,sizeof(x)) #define maxn 6005 #define ll long long #define eps 1e-6 #define inf int(1e9) using namespace std; struct data{int pre,obj; }e[60005]; struct node{int h,x,y; }a[maxn]; int tot,h,n,m,idx,cnt,ans,t; int head[maxn],bin[22],used[maxn],mat[maxn],vis[maxn]; ll read(){ ll x=0,f=1; char ch=getchar(); while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();} while (isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();} return x*f; } void insert(int x,int y){ e[++tot].pre=head[x]; e[tot].obj=y; head[x]=tot; } bool find(int u){ for (int j=head[u];j;j=e[j].pre){ int v=e[j].obj; if (vis[v]==idx) continue; vis[v]=idx; if (!mat[v]||find(mat[v])) {mat[v]=u; return 1;} } return 0; } void get(int o,int i,int j){ if (n<=h&&n<=m) swap(o,i); else if (m<=h&&m<=n) swap(o,j); a[++cnt]=(node){o,i,j}; } void dfs(int dep,int sum){ if (sum>=ans) return; if (dep>h){ rep(i,1,n) head[i]=0; rep(i,1,m) mat[i]=0,vis[i]=0; tot=0; idx=0; rep(i,1,cnt) if (!used[a[i].h]) insert(a[i].x,a[i].y); rep(i,1,n){ idx++; sum+=find(i); if (sum>=ans) return; } ans=min(ans,sum); return; } used[dep]=1; dfs(dep+1,sum+1); used[dep]=0; dfs(dep+1,sum); } int main(){ t=read(); bin[0]=1; rep(i,1,20) bin[i]=bin[i-1]*2; while (t--){ cnt=0; h=read(); n=read(); m=read(); rep(o,1,h) rep(i,1,n) rep(j,1,m) { int x=read(); if (x==1) get(o,i,j); } if (n<=h&&n<=m) swap(n,h); else if (m<=h&&m<=n) swap(m,h); ans=h; dfs(1,0); printf("%d ",ans); } return 0; }