Description：

一个 $a\times b\times c$ 的长方体，每次可以覆盖 $x\times y\times z$ 的大小，花费为 $min(x,y,z)$ ，求最小可以花费多少把所有标记的点都覆盖。

$a\times b\times c\le 5000$

Solution：

首先发现一片一片覆盖一定是最值的，也就是说最终解一定是选出了很多厚度为 $1$ 的片。

发现 $\sqrt[3]{5000}\approx 17$ ， $\sqrt{5000}\approx 70$ ，将 $a$ ， $b$ ， $c$ 排序，一定有 $a\le 17$ ， $b\le 70$ ，于是可以暴力枚举 $a$ 维选了哪些片，将没选的点压到二维上，于是问题就转化成了在二维平面网格图上有一些点选出一些横或竖的长条把他们全覆盖，把行看成左部点，把列看成右部点，在有点的行和列之间连边，就是一个最小点覆盖，匈牙利求最大匹配即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int a,b,c;

#define MAXN 5010

int p[4][MAXN],ptr = 0;

int cnt[1 << 18];

int lowbit(int x){return x&(-x);}

struct edge

{

    int to,nxt;

}e[MAXN];

int edgenum = 0;

int lin[75] = {0};

void add(int a,int b)

{

    ++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

    return;

}

int v[75],cur = 0;

int match[75];

bool find(int k)

{

    for(int i = lin[k];i != 0;i = e[i].nxt)

    {

        if(v[e[i].to] != cur)

        {

            v[e[i].to] = cur;

            if(match[e[i].to] == -1 || find(match[e[i].to]))

            {

                match[e[i].to] = k;

                return true;

            }

        }

    }

    return false;

}

void work()

{

    memset(e,0,sizeof(e));

    memset(lin,0,sizeof(lin));

    edgenum = 0;

    scanf("%d%d%d",&a,&b,&c);

    int t;

    ptr = 0;

    for(int i = 1;i <= a;++i)

    {

        for(int j = 1;j <= b;++j)

        {

            for(int k = 1;k <= c;++k)

            {

                scanf("%d",&t);

                if(t == 1)

                {

                    ++ptr;

                    p[1][ptr] = i;

                    p[2][ptr] = j;

                    p[3][ptr] = k;

                }

            }

        }

    }

    if(a > b){swap(a,b);swap(p[1],p[2]);}

    if(a > c){swap(a,c);swap(p[1],p[3]);}

    if(b > c){swap(b,c);swap(p[2],p[3]);}

    int tot = (1 << a) - 1;

    int ans = 0x3f3f3f3f;

    for(int t = 0;t <= tot;++t)

    {

        if(t != 0)cnt[t] = cnt[t ^ lowbit(t)] + 1;

        memset(lin,0,sizeof(lin));

        edgenum = 0;

        for(int i = 1;i <= ptr;++i)

        {

            if(t & (1 << (p[1][i] - 1)))continue;

            add(p[2][i],p[3][i]);

        }

        memset(match,-1,sizeof(match));

        memset(v,0,sizeof(v));

        cur = 0;

        int res = 0;

        for(int i = 1;i <= b;++i)

        {

            ++cur;

            if(find(i))++res;

        }

        ans = min(ans,cnt[t] + res);

    }

    cout << ans << endl;

    return;

}

int main()

{

    int testcases;

    scanf("%d",&testcases);

    while(testcases--)work();

    return 0;

}