考虑贪心，控制某一维为1，另两位最大是最优的，也就是一次选一个厚度为1的面
那么对于每个点，可以有3种面是可以选到它的
然后gg
考虑二维的状态，一个平面，有些点，一次选一行或一列最优
那么每一个点i，j可以被行i和列j选中，将i->j连接一条边，每一条边就代表一个点
选取最少的点覆盖所有边就是最少点覆盖=最大匹配
因为a*b*c<=5000所以最小的那一维一定<=17，可以枚举这一维哪些面被一次清除，
#include <cstdio>
#include <cstring>
#include <iostream>
#define N 5001 using namespace std; int T, a, b, c, n, ans, cnt;
int now[N][N], head[N], to[N * N], nex[N * N], belong[N];
bool vis[N]; struct node
{
int x, y, z;
node(int x = 0, int y = 0, int z = 0) : x(x), y(y), z(z) {}
}p[N]; inline int read()
{
int x = 0, f = 1;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) x = (x << 1) + (x << 3) + ch - '0';
return x * f;
} inline void clear()
{
int i;
ans = cnt = 0;
for(i = 1; i <= b; i++) head[i] = -1;
for(i = 1; i <= c; i++) belong[i] = 0;
} inline void add(int x, int y)
{
to[cnt] = y;
nex[cnt] = head[x];
head[x] = cnt++;
} inline bool dfs(int u)
{
int i, v;
for(i = head[u]; ~i; i = nex[i])
{
v = to[i];
if(!vis[v])
{
vis[v] = 1;
if(!belong[v] || dfs(belong[v]))
{
belong[v] = u;
return 1;
}
}
}
return 0;
} inline int solve()
{
int i, j, k, ret = 1e9;
for(k = 0; k < (1 << a); k++)
{
clear();
for(i = k; i; i >>= 1)
if(i & 1) ans++;
for(i = 1; i <= n; i++)
if(!(k & (1 << p[i].x - 1))) now[p[i].y][p[i].z] = 1;
for(i = 1; i <= b; i++)
for(j = 1; j <= c; j++)
if(now[i][j]) add(i, j);
for(i = 1; i <= b; i++)
{
for(j = 1; j <= c; j++) vis[j] = 0;
ans += dfs(i);
}
ret = min(ret, ans);
for(i = 1; i <= n; i++)
if(!(k & (1 << p[i].x - 1))) now[p[i].y][p[i].z] = 0;
}
return ret;
} int main()
{
int i, j, k, x;
T = read();
while(T--)
{
n = 0;
a = read();
b = read();
c = read();
for(i = 1; i <= a; i++)
for(j = 1; j <= b; j++)
for(k = 1; k <= c; k++)
{
x = read();
if(x) p[++n] = node(i, j, k);
}
if(c < a && c < b)
{
swap(a, c);
for(i = 1; i <= n; i++) swap(p[i].x, p[i].z);
}
else if(b < c && b < a)
{
swap(a, b);
for(i = 1; i <= n; i++) swap(p[i].x, p[i].y);
}
printf("%d\n", solve());
}
return 0;
}
剩余的面压缩到一起，连边跑匈牙利