Description

最近在生物实验室工作的小 T 遇到了大麻烦.

由于实验室最近升级的缘故, 他的分格实验皿是一个长方体, 其尺寸为 \(a \times b \times c\), 其中 \(a, b, c \in \mathbb{Z}^{+}\). 为了实验的方便, 它被划分为 \(a \times b \times c\) 个单位立方体区域, 每个单位立方体尺寸为 \(1 \times 1 \times 1\). 用 \((i, j, k)\) 标识一个单位立方体,\(1 \leq i \leq a, 1 \leq j \leq b, q \leq k \leq c\). 这个 实验皿已经很久没有人用了, 现在, 小 T 被导师要求将其中一些单位立方体区域进行消毒操作 (每个区域可以被重复消毒). 而由于严格的实验要求, 他被要求使用一种特定的 F 试剂来进行消毒. 这种 F 试剂特别奇怪, 每次对尺寸为 \(x \times y \times z\) 的长方体区域 (它由 \(x \times y \times z\) 个单位立方体组成) 进行消毒时, 只需要使用 \(min\{x, y, z\}\) 单位的 F 试剂. F 试剂的价格不菲, 这可难倒了小 T. 现在请你告诉他, 最少要用多少单位的 F 试剂.

Input

第一行是一个正整数 \(T\), 表示数据组数.

接下来是 \(T\) 组数据, 每组数据开头是三个数 \(a, b, c\) 表示实验皿的尺寸.

接下来会出现 \(a\) 个 \(b\) 行 \(c\) 列的用空格隔开的 \(01\) 矩阵,\(0\) 表示对应的单位立方体不要求消毒,\(1\) 表示对应的单位立方体需要消毒;

Output

仅包含 D 行, 每行一个整数, 表示对应实验皿最少要用多少单位的 F 试剂.

Sample Input

1
4 4 4
1 0 1 1
0 0 1 1
0 0 0 0
0 0 0 0
0 0 1 1
1 0 1 1
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 0 0 0

Sample Output

3

Data Range

输入保证满足 \(a \times b \times c \leq 5000, T \leq 3\).

Explanation

所有那些标记为 \(0\) 的方块都是来打酱油的, 无视他们......

只有 \(1\) 有作用, 并且不超过 \(5000\) 个, 这暗含了条件 \(n \leq 5000\).

我们会贪心地希望整个立方体越扁平越好, 因为需要最小化某一条最窄的边. 进一步, 加厚 染色区域对总结果没有更好的影响, 在最好的情形下只会维持原状, 糟糕的情形下会使答案 加大.

我们按照三个坐标轴排序 (需要预处理 orientation), 然后 dfs 留下还是不留下某一块, 最后用二分图匹配跑一遍寻找最小 (雾) 匹配.

注意在二分图重置时切记不要使用 memset(...), 因为这导致了过多的时间浪费, 其实有很大一部分内存是不需要被清理的, 白白增大了常数.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
const int maxn = 10010, maxm = 100100;

class HungaryMatch
{
public:
    struct edge
    {
        int u, v;
        edge *next;
    };
    int n, ecnt, vis_targ;
    edge *edges[maxn], epool[maxn];
    int vis[maxn], from[maxn];
    void add_edge(int u, int v)
    {
        edge *p = &epool[++ecnt];
        p->u = u; p->v = v;
        p->next = edges[u]; edges[u] = p;
        return ;
    }
    bool find(int p)
    {
        for (edge *ep = edges[p]; ep; ep = ep->next)
            if (vis[ep->v] != vis_targ) {
                vis[ep->v] = vis_targ;
                if (from[ep->v] == 0 || find(from[ep->v])) {
                    from[ep->v] = p;
                    return true;
                }
            }
        return false;
    }
    void init(int n)
    {
        // Some fast and non-time-consuming init methods
        // Never use memset(...) here!
        this->n = n;
        for (int i = 0; i <= n; i++)
            edges[i] = NULL;
        for (int i = 0; i <= n; i++)
            from[i] = 0;
        ecnt = 0;
        vis_targ += 1;
        return ;
    }
} graph;

int T;
int a, b, c, tot, res;
int used[maxn];

struct point { int x, y, z;
    point(void) { return ; }
    point(int _1, int _2, int _3) {
        x = _1; y = _2; z = _3;
        if (b <= a && b <= c) swap(x, y);
        else if (c <= a && c <= b) swap(z, x);
        return ; }
} pnt[maxn];


void dfs(int pos, int cnt) // cnt: layers coloured on x-axis
{
    if (cnt >= res) {
        return ;
    } else if (pos > a) {
        graph.init(b);
        for (int i = 1; i <= tot; i++)
            if (!used[pnt[i].x])
                graph.add_edge(pnt[i].y, pnt[i].z);
        for (int i = 1; i <= b; i++) {
            graph.vis_targ += 1;
            cnt += graph.find(i);
            if (cnt >= res)
                return ;
        }
        res = cnt;
        return ;
    }
    used[pos] = true;
    dfs(pos + 1, cnt + 1);
    used[pos] = false;
    dfs(pos + 1, cnt);
    return ;
}

int main(int argc, char** argv)
{
    scanf("%d", &T);
    for (int idx = 1; idx <= T; idx++) {
        scanf("%d%d%d", &a, &b, &c);
        tot = 0;
        rep(i, 1, a) rep(j, 1, b) rep(k, 1, c) {
            int x; scanf("%d", &x);
            if (x == 1) pnt[++tot] = point(i, j, k);
        }
        if (b <= a && b <= c) swap(a, b);
        else if (c <= a && c <= b) swap(c, a);
        res = a;
        dfs(1, 0);
        printf("%d\n", res);
    }
    return 0;
}