题解

思路分析

这是一道 状态压缩 + 二分图匹配 的三维几何覆盖问题。

问题建模

• 在 $a \times b \times c$ 的立方体中消毒指定的单位立方体
• 每次消毒一个 $x \times y \times z$ 的长方体，花费 $\min(x, y, z)$
• 求最小总花费

核心思路

1. 维度转换

关键观察：要最小化花费，应该让 $\min(x, y, z)$ 尽可能大。

策略：

• 将最小维度（$a, b, c$ 中最小的）作为枚举维度
• 问题转化为二维平面的覆盖

2. 状态压缩枚举

假设 $a$ 是最小维度（$a \leq b, c$）：

• 枚举 $a$ 维度的所有子集（哪些层被选中）
• 对于每个子集，问题变成在 $b \times c$ 平面上用矩形覆盖指定点

3. 二分图最大匹配

对于固定的层子集，在 $b \times c$ 平面上：

• 每个需要消毒的点是一个顶点
• 如果两个点在同一行或同一列，连一条边
• 求最小覆盖 = 点数 - 最大匹配（König定理）

匈牙利算法 求最大匹配。

4. 答案计算

枚举所有子集，取最小值。

算法步骤

1. 预处理：

   • 读入所有需要消毒的点
   • 确定最小维度并交换坐标轴

2. 枚举层子集（$2^a$ 种）：

   • 对于每个子集，构建二分图
   • 跑匈牙利算法求最大匹配
   • 计算花费并更新答案

3. 输出答案

复杂度分析

• 枚举子集：$O(2^a)$
• 匈牙利算法：$O(bc \cdot \sqrt{bc})$
• 总时间复杂度：$O(2^a \cdot bc\sqrt{bc})$
• 空间复杂度：$O(abc)$

由于 $abc \leq 5000$ 且 $a$ 是最小维度，复杂度可以接受。

#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;
}

题解

把病毒所在的细菌培养皿看成一个 $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;
}