题解

把病毒所在的细菌培养皿看成一个 $a \times b \times c$ 的三维网格。任意一个细胞可以通过消毒其所在的 $x$ 轴平面、$y$ 轴平面或 $z$ 轴平面来清除。由于我们要最小化被消毒的平面数量，可以先枚举在 $x$ 方向上要消毒的平面集合，剩余仍然含病毒的细胞就必须在 $y$、$z$ 两个方向上额外选择平面覆盖。

对固定的 $x$ 平面集合，剩余所有细胞都位于某个 $(y,z)$ 二维坐标，可以把所有 “还没被消毒的细胞” 看作二分图中的边：左部是 $b$ 个 $y$ 平面、右部是 $c$ 个 $z$ 平面，若坐标 $(x,y,z)$ 上仍有病毒，则连接 $y$ 与 $z$。为了覆盖所有边，需要在左右两侧再选若干平面。根据 Kőnig 定理，最小点覆盖数等于最大匹配数，于是我们只要在这个二分图中求最大匹配，再把匹配大小与已经选过的 $x$ 平面数量相加即可得到本次枚举的消毒代价。

由于维度不超过 20，我们先将三维数组按最短的一维作为“枚举维”，通过交换坐标把问题约化到最多枚举 $2^{\min(a,b,c)}$ 个子集。对于每个子集，重建左右两侧的邻接表，调用匈牙利算法做最大匹配即可。整体复杂度约为 $O(2^{\min(a,b,c)} \cdot (b+c) \cdot \text{匹配复杂度})$，足以通过数据范围。

#include <bits/stdc++.h>
using namespace std;
int T,hea[5005],cnt,a,b,c,mi,sx[4][5005],uu,ans,lnk[5005],qaq;
bool isn[5005],qwq[25],vis[5005];
struct Edge{
    int v,nxt;
}edge[5005];
void add(int u,int v){
    edge[++cnt].nxt=hea[u];
    edge[cnt].v=v;
    hea[u]=cnt;
}
bool dfs(int x){
    for(int i=hea[x];i;i=edge[i].nxt){
        int t=edge[i].v;
        if(!vis[t]){
            vis[t]=true;
            if(!lnk[t]||dfs(lnk[t])){
                lnk[t]=x;
                return true;
            }
        }
    }
    return false;
}
void work(int x){
    for(int i=1;i<=b;i++) hea[i]=0;
    cnt=0;
    for(int i=1;i<=c;i++) lnk[i]=0;
    int tmp=0;
    for(int i=0;i<a;i++){
        if(x&(1<<i)) qwq[i+1]=false,tmp++;
        else qwq[i+1]=true;
    }
    for(int i=1;i<=qaq;i++)
        if(qwq[sx[1][i]])
            add(sx[2][i],sx[3][i]);
    for(int i=1;i<=b;i++){
        for(int j=1;j<=c;j++) vis[j]=false;
        if(dfs(i)) tmp++;
    }
    ans=min(tmp,ans);
}
int main(){
    cin>>T;
    while(T--){
        qaq=0;
        ans=0x3f3f3f3f;
        scanf("%d%d%d",&a,&b,&c);
        mi=min(a,min(b,c));
        for(int i=1;i<=a;i++)
            for(int j=1;j<=b;j++)
                for(int k=1;k<=c;k++){
                    scanf("%d",&uu);
                    if(!uu) continue;
                    sx[1][++qaq]=i;
                    sx[2][qaq]=j;
                    sx[3][qaq]=k;
                }
        if(mi==b) swap(a,b),swap(sx[1],sx[2]);
        else if(mi==c) swap(a,c),swap(sx[1],sx[3]);
        for(int i=0;i<(1<<a);i++)
            work(i);
        printf("%d\n",ans);
    }
    return 0;
}