http://www.lydsy.com/JudgeOnline/problem.php?id=3140
如果只有两维，那就是二分图最小点覆盖
现在是三维，但是a*b*c<=5000，说明最小的那一维不会超过17
将最小的那一维作为正方形的高
然后枚举要消哪些层，剩下的层看成一层 做最小点覆盖
注意卡常
#include<cstdio>
#include<cstring>
#include<iostream> using namespace std; #define N 5001 struct node
{
int i,j,k;
}e[N]; bool have[]; int front[N],to[N],nxt[N],tot;7 int match[N];
int tim,vis[N]; void read(int &x)
{
x=; char c=getchar();
while(!isdigit(c)) c=getchar();
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
} bool go(int u)
{
int v;
for(int i=front[u];i;i=nxt[i])
{
v=to[i];
if(vis[v]!=tim)
{
vis[v]=tim;
if(!match[v] || go(match[v]))
{
match[v]=u;
return true;
}
}
}
return false;
} int count(int x)
{
int sum=;
while(x) sum+=x&,x>>=;
return sum;
} void add(int u,int v)
{
to[++tot]=v; nxt[tot]=front[u]; front[u]=tot;
} int main()
{
int T,a,b,c;
int ty,x;
int S,cnt; bool tag;
int ans,now;
read(T);
while(T--)
{
read(a); read(b); read(c);
if(a<=b && a<=c) ty=;
else if(b<=a && b<=c) ty=;
else ty=;
memset(have,false,sizeof(have));
cnt=;
for(int i=;i<=a;++i)
for(int j=;j<=b;++j)
for(int k=;k<=c;++k)
{
read(x);
if(!x) continue;
cnt++;
if(ty==) e[cnt].i=i,e[cnt].j=j,e[cnt].k=k;
if(ty==) e[cnt].i=j,e[cnt].j=i,e[cnt].k=k;
if(ty==) e[cnt].i=k,e[cnt].j=i,e[cnt].k=j;
have[e[cnt].i]=true;
}
if(ty==) swap(a,b);
else if(ty==) swap(b,c),swap(a,b);
ans=a;
S=<<a;
for(int s=;s<S;++s)
{
tag=true;
for(int i=;i<=a && tag;++i)
if(<<i-&s && !have[i]) tag=false;
if(!tag) continue;
now=count(s);
tot=;
memset(front,,sizeof(*front)*(b+));
for(int i=;i<=cnt;++i)
if(!(<<e[i].i-&s)) add(e[i].j,e[i].k);
memset(match,,sizeof(*match)*(c+));
for(int i=;i<=b;++i)
{
tim++;
if(go(i)) now++;
if(now>=ans) break;
}
ans=ans<=now ? ans : now;
}
printf("%d\n",ans);
}
}