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 5001struct node {int i,j,k; }e[N];bool have[18];int front[N],to[N],nxt[N],tot;7int match[N]; int tim,vis[N];void read(int &x) {x=0; char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)) { x=x*10+c-'0'; 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=0;while(x) sum+=x&1,x>>=1;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=1;else if(b<=a && b<=c) ty=2;else ty=3;memset(have,false,sizeof(have));cnt=0;for(int i=1;i<=a;++i)for(int j=1;j<=b;++j)for(int k=1;k<=c;++k){read(x);if(!x) continue;cnt++;if(ty==1) e[cnt].i=i,e[cnt].j=j,e[cnt].k=k;if(ty==2) e[cnt].i=j,e[cnt].j=i,e[cnt].k=k;if(ty==3) e[cnt].i=k,e[cnt].j=i,e[cnt].k=j;have[e[cnt].i]=true;}if(ty==2) swap(a,b);else if(ty==3) swap(b,c),swap(a,b);ans=a;S=1<<a;for(int s=0;s<S;++s){tag=true;for(int i=1;i<=a && tag;++i)if(1<<i-1&s && !have[i]) tag=false;if(!tag) continue;now=count(s);tot=0;memset(front,0,sizeof(*front)*(b+1));for(int i=1;i<=cnt;++i)if(!(1<<e[i].i-1&s)) add(e[i].j,e[i].k);memset(match,0,sizeof(*match)*(c+1));for(int i=1;i<=b;++i){tim++;if(go(i)) now++;if(now>=ans) break;}ans=ans<=now ? ans : now;}printf("%d\n",ans);} }
