1 /**************************************************************  2     Problem: 3140  3     User: rausen  4     Language: C++  5     Result: Accepted  6     Time:1324 ms  7     Memory:1312 kb  8 ****************************************************************/  9   10 #include <cstdio> 11 #include <algorithm> 12 #include <cstring> 13   14 using namespace std; 15 const int N = 5005; 16   17 int a, b, c, ans; 18 int first[N], tot, cnt_p, now_time; 19 int l[N], vis[N]; 20 bool u[20]; 21   22 struct point { 23   int x, y, z; 24   point() {} 25   point(int _x, int _y, int _z) : x(_x), y(_y), z(_z) { 26     if (b <= a && b <= c) swap(x, y); else 27     if (c <= a && c <= b) swap(x, z); 28   } 29 } p[N]; 30   31 struct edge { 32   int next, to; 33   edge() {} 34   edge(int _n, int _t) : next(_n), to(_t) {} 35 } e[N * 10]; 36   37 int read() { 38   int x = 0; 39   char ch = getchar(); 40   while (ch < ‘0‘ || ‘9‘ < ch) 41     ch = getchar(); 42   while (‘0‘ <= ch && ch <= ‘9‘) 43     (x *= 10) += ch - ‘0‘, ch = getchar(); 44   return x; 45 } 46   47 inline void add_edge(int x, int y) { 48   e[++tot] = edge(first[x], y), first[x] = tot; 49 } 50   51 #define y e[x].to 52 bool find(int p) { 53   int x; 54   for (x = first[p]; x; x = e[x].next) 55     if (vis[y] != now_time) { 56       vis[y] = now_time; 57       if (!l[y] || find(l[y])) { 58     l[y] = p; 59     return 1; 60       } 61     } 62   return 0; 63 } 64 #undef y 65   66 inline void work(int res) { 67   int i; 68   tot = 0; 69   for (i = 1; i <= b; ++i) first[i] = 0; 70   for (i = 1; i <= c; ++i) l[i + b] = 0; 71   for (i = 1; i <= cnt_p; ++i) 72     if (!u[p[i].x]) 73       add_edge(p[i].y, p[i].z + b); 74   for (i = 1; i <= b; ++i) { 75     ++now_time; 76     if ((res += find(i)) > ans) return; 77   } 78   ans = res; 79 } 80   81 void dfs(int step, int now_ans) { 82   if (now_ans > ans) return; 83   if (step > a) { 84     work(now_ans); 85     return; 86   } 87   u[step] = 1, dfs(step + 1, now_ans + 1); 88   u[step] = 0, dfs(step + 1, now_ans); 89 } 90   91 int main() { 92   int i, j, k, T; 93   T = read(); 94   while (T--) { 95     a = read(), b = read(), c = read(), cnt_p = 0; 96     for (i = 1; i <= a; ++i) 97       for (j = 1; j <= b; ++j) 98     for (k = 1; k <= c; ++k) 99       if (read()) p[++cnt_p] = point(i, j, k);100     if (b <= a && b <= c) swap(a, b); else101     if (c <= a && c <= b) swap(a, c);102     ans = a;103     dfs(1, 0);104     printf("%d\n", ans);105   }106   return 0;107 }