Luogu

分析

先考虑平面上的这种问题：平面上有一些方块，你每次可以覆盖长度为 $x$、宽度为 $y$ 的一个区域，代价是 $\min(x,y)$，求覆盖所有点的最小代价。

显然每次染一个 $1\times k$ 的区域是最优的。于是让每个方块的 $x$ 向 $y$ 连边，然后求二分图最小点覆盖即可。

现在把这个扩展到三维。

注意到一定有一维 $\leq\sqrt[3]{5000}$ 也就是 $\leq 17$ 。不妨假设这一维是 $a$ 。

然后，对于每一层有两种情况：直接消掉这一层，或者和其它某些面做 $1\times 1\times k$ 的消除。

对于后一种层，将其拍扁成二维，就变成了上面的问题。

我们只需要 $\mathcal{O}(2^{17})$ 枚举每层的情况即可。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=5000+10;

struct Edge { int v,nxt; } e[N];
int head[N],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

int a,b,c,tot,ans,tim;
int g[4][N],mark[N];
int vis[N],lnk[N];

inline int Hungary(int u) {
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (vis[v]==tim) continue;
        vis[v]=tim;
        if (!lnk[v]||Hungary(lnk[v])) return lnk[v]=u;
    }
    return 0;
}

inline void solve(int S) {
    for (re int i=1;i<=b;++i) head[i]=0; cnt=0;
    for (re int i=1;i<=c;++i) lnk[i]=0;
    int now=0;
    for (re int i=1;i<=a;++i) {
        if (S&(1<<(i-1))) mark[i]=0,++now;
        else mark[i]=1;
    }
    for (re int i=1;i<=tot;++i)
        if (mark[g[1][i]]) addEdge(g[2][i],g[3][i]);
    for (re int i=1;i<=b;++i) {
        ++tim;
        if (Hungary(i)) ++now;
        if (now>=ans) break;
    }
    ans=min(ans,now);
}

int main() {
    int T=read();
    while (T--) {
        a=read(),b=read(),c=read(),tot=0,ans=1e9;
        for (re int i=1;i<=a;++i)
            for (re int j=1;j<=b;++j) 
                for (re int k=1;k<=c;++k) {
                    if (!read()) continue;
                    g[1][++tot]=i,g[2][tot]=j,g[3][tot]=k;
                }
        if (b<a&&b<c) swap(a,b),swap(g[1],g[2]);
        else if (c<a&&c<b) swap(a,c),swap(g[1],g[3]);
        for (re int S=0;S<(1<<a);++S) solve(S);
        printf("%d\n",ans);
    }
    return 0;
}