[BZOJ 3140] 消毒

Link:

BZOJ 3140 传送门

Solution:

挺好的一道暴力题

首先发现可以每次贪心选择宽度为1的一面，即$1*x*y,1*x*z,1*y*z$

那么对于与该面垂直的面，相当于解决了一行/一列

于是我们可以先考虑一个二维问题：

每次选取一行/一列要耗费一个代价，询问要覆盖所有染色点需要多大代价

由于对于每个点的横纵坐标都是映射关系，且横/纵坐标是两个独立的集合

于是将染色点的横/纵坐标连边后问题转化为最小点覆盖问题，也就是二分图最大匹配

为了将三维问题转化为当前可做的二维问题，就只能对一维暴力处理了：

由于$x*y*zle 5000$，因此其中至少有一维长度小于17

对于这一维我们状压枚举进行涂色的切面，那么解决剩下节点的切面都与该维切面垂直

问题就转换成了上述的二维问题，只不过点数多了一些且可能重复

Code:

#include <bits/stdc++.h>

using namespace std;
const int MAXN=5005;
struct edge{int nxt,to;}e[MAXN<<2];
struct node{int x,y,z;}dat[MAXN];
int T,x,y,z,mn,head[MAXN],vis[MAXN],mat[MAXN],used[MAXN],res,tot,cnt,idx=1;

void add_edge(int from,int to)//注意别加成2条边了…… 
{e[++tot].nxt=head[from];e[tot].to=to;head[from]=tot;}

int dfs(int x)
{
    vis[x]=idx;
    for(int i=head[x];i;i=e[i].nxt)
    {
        int v=e[i].to,m=mat[v];
        if(m==-1||vis[m]!=idx&&dfs(m))
        {mat[v]=x;return 1;}
    }
    return 0;
}

void solve(int k)
{
    tot=0;int sum=0;
    for(int i=0;i<=x;i++) used[i]=0;
    for(int i=0;i<=y;i++) head[i]=0;
    for(int i=0;i<=z;i++) mat[i]=-1;
    
    for(int i=0;i<x;i++)
        if(k&(1<<i)) used[i+1]=1,sum++;
    for(int i=1;i<=cnt;i++)
        if(!used[dat[i].x])
            add_edge(dat[i].y,dat[i].z);
    
    for(int i=1;i<=y;i++,idx++) sum+=dfs(i);
    res=min(res,sum);
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&x,&y,&z);
        cnt=0;res=1<<30;
        mn=min(x,min(y,z));
        for(int i=1;i<=x;i++)
            for(int j=1;j<=y;j++)
                for(int k=1;k<=z;k++)
                {
                    int t;scanf("%d",&t);
                    if(t) dat[++cnt]={i,j,k};
                }
        if(mn==y)
        {swap(x,y);for(int i=1;i<=cnt;i++) swap(dat[i].x,dat[i].y);}
        if(mn==z) 
        {swap(x,z);for(int i=1;i<=cnt;i++) swap(dat[i].x,dat[i].z);}
        
        for(int i=0;i<(1<<x);i++) solve(i);
        printf("%d
",res);
    }
    return 0;
}