难度：省选/NOI-

题目描述

        最近在生物实验室工作的小T遇到了大麻烦。由于实验室最近升级的缘故，他的分格实验皿是一个长方体,其尺寸为$abc$，$a、b、c$均为正整数。为了实验的方便，它被划分为$abc$个单位立方体区域，每个单位立方体尺寸为$1$。用$(i,j,k)$标识一个单位立方体，$1<=i<=a，1<=j<=b，1<=k<=c$。这个实验皿已经很久没有人用了，现在，小T被导师要求将其中一些单位立方体区域进行消毒操作（每个区域可以被重复消毒）。
        而由于严格的实验要求，他被要求使用一种特定的F试剂来进行消毒。 这种F试剂特别奇怪，每次对尺寸为$xyz$的长方体区域（它由$xyz$个单位立方体组 成）进行消毒时，只需要使用$min\{x,y,z\}$单位的F试剂。F试剂的价格不菲，这可难倒了小T。
        现在请你告诉他，最少要用多少单位的F试剂。(注：$min\{x,y,z\}$表示x、y、z中的最小者。)

输入输出格式

输入格式：

        第一行是一个正整数D，表示数据组数。接下来是D组数据，每组数据开头是三个数$a,b,c$表示实验皿的尺寸。接下来会出现$a$个$b$行$c$列的用空格隔开的01矩阵，0表示对应的单位立方体不要求消毒，1表示对应的单位立方体需要消毒；例如，如果第1个01矩阵的第2行第3列为1，则表示单位立方体$(1,2,3)$需要被消毒。输入保证满足$abc<=5000,T<=3$。

输出格式：

        仅包含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

题解

        还算比较简单的二分图问题。首先将问题简化，看二维平面上的结论。
        对于二维平面上的点，将每一个值为1的点的横坐标值向纵坐标连一条边，可以得到一个二分图。注意到每选取一条边（对应一个点）就相当于选取了其所在的一行或者一列（因为F试剂的量只看最小的坐标值，故直接选一行或一列能尽可能利用其带来的价值）。由于需要覆盖所有的点，在二分图上就是覆盖所有的边，问题便转化为求二分图的最小点覆盖，直接套板子即可。
        三维的情景较二维更麻烦。对于一个平面，如果我们仍利用二维平面上的结论，就会选取这个平面上的几个横向区域和纵向区域，它们消耗的试剂都是1，这样即使将这些区域向第三维上无限扩展，试剂量也不会增加。于是就有了一个思路：将三维的所有点全部压至一个平面上处理，转化为二维平面上的问题。
        这样做显然是不对的，比如当某个平面上全是点而其它平面上没有点时，选用第三维坐标去覆盖就会更优。于是另一个思路产生：暴力枚举哪些平面需要一次性处理（覆盖其所在的整个平面，消耗试剂量1），然后剩下的压扁成一个二维平面，之后求和，取最小值。
        由于$abc≤5000$，可知至少有一个坐标不超过17，那么枚举需要$2^{17}$次循环，每一次再进行一遍二分图匹配，在时间复杂度上说得过去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>

#define N 5001
using namespace std;
struct node {
    int i, j, k;
} ele[N];
struct Edge {
    int to, next;
} edge[N];
bool isOK[18], lk;
int head[N], D, a, b, c, type, cnt = 1, ans, now, be[N], vis[N], pp;

inline int read() {
    int s = 0;
    char e = getchar();
    while (e < '-')e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return s;
}

int f(int x) {
    for (int i = head[x]; i; i = edge[i].next) {
        if (vis[edge[i].to] == 0) {
            vis[edge[i].to] = 1;
            if (!be[edge[i].to] || f(be[edge[i].to])) {
                be[edge[i].to] = x;
                return 1;
            }
        }
    }
    return 0;
}

void add(int x, int y) {
    edge[pp].to = y, edge[pp].next = head[x], head[x] = pp++;
}

int main() {
    D = read();
    while (D--) {
        a = read(), b = read(), c = read();
        if (a <= b && a <= c) type = 1;
        else if (b <= a && b <= c) type = 2;
        else type = 3;
        memset(isOK, false, sizeof(isOK)), cnt = 1;
        for (int i = 1; i <= a; ++i)
            for (int j = 1; j <= b; ++j)
                for (int k = 1; k <= c; ++k) {
                    if (!read()) continue;
                    if (type == 1) ele[cnt].i = i, ele[cnt].j = j, ele[cnt].k = k;
                    if (type == 2) ele[cnt].i = j, ele[cnt].j = i, ele[cnt].k = k;
                    if (type == 3) ele[cnt].i = k, ele[cnt].j = i, ele[cnt].k = j;
                    isOK[ele[cnt].i] = true, ++cnt;
                }
        if (type == 2) swap(a, b);
        else if (type == 3) swap(b, c), swap(a, b);
        ans = a;
        for (int s = 0; s < (1 << a); ++s) {
            lk = true, now = 0;
            for (int i = 1; i <= a && lk; ++i)
                if (((1 << (i - 1)) & s) && !isOK[i]) {
                    lk = false;
                    break;
                }
            if (!lk) continue;
            for (int p = 0; p < a; p++)if ((1 << p) & s)++now;
            memset(head, 0, sizeof(head)), memset(be, 0, sizeof(be)), pp = 1;
            for (int i = 1; i < cnt; i++)
                if (!((1 << (ele[i].i - 1)) & s)) add(ele[i].j, ele[i].k);
            for (int i = 1; i <= b; i++) {
                memset(vis, 0, sizeof(vis)), now += f(i);
                if (now >= ans) break;
            }
            ans = min(ans, now);
        }
        printf("%d\n", ans);
    }
    return 0;
}