「HNOI 2013」消毒

题目链接

戳我

\(Solution\)

我们首先想一想如果这一题只是二维的该怎么办?

就是一个最小点覆盖问题.这里就不详细解释了,用网络流或匈牙利都无所谓.

但现在是三维的,那么现在该如何处理呢?

我们发现\(a*b*c<=5000\),所以必定有一个要小于\(\sqrt[3]{5000}\)

所以我们可以枚举最小的一维的状态,那一维已经消了,还是没消.

对于没消的直接如同二维的跑最小点覆盖就好了.

但是\(bzoj\)实在卡不过去

\(Code\)

#include<bits/stdc++.h>

#define inf 1e9

using namespace std;

typedef long long ll;

int read(){

    int x=0,f=1;

    char c=getchar();

    while(c<'0'||c>'9')

        f=(c=='-')?-1:1,c=getchar();

    while(c>='0'&&c<='9')

        x=x*10+c-'0',c=getchar();

    return x*f;

}

#define re register

struct node{

    int to,next,v;

}a[200001];

int S[100001],ss[100001],vis[100001],bj[50],bin[50],head[100001],dep[10001],cnt,n,m,s,t,x,y,z,A,B,C,res,Min,minx,tot,hh,maxx,cur[100010];

inline void add(re int x,re int y,re int c){

    a[++cnt].to=y,a[cnt].next=head[x],a[cnt].v=c,head[x]=cnt;

    a[++cnt].to=x,a[cnt].next=head[y],a[cnt].v=0,head[y]=cnt;

}

queue<int> q;

inline int bfs(){

    for(int i=s;i<=t;i++)

    dep[i]=0;

    q.push(s);

    dep[s]=1;

    while(!q.empty()){

        re int now=q.front();

        q.pop();

        for(re int i=head[now];i;i=a[i].next){

            re int v=a[i].to;

            if(!dep[v]&&a[i].v>0)

                dep[v]=dep[now]+1,q.push(v);

        }

    }

    if(dep[t])

        return 1;

    return 0;

}

int dfs(int k,int list) {

    if(k==t||!list)

        return list;

    int flow=0;

    for(int &i=cur[k]; i; i=a[i].next) {

        int v=a[i].to;

        if(dep[v]==dep[k]+1&&a[i].v) {

            int p=dfs(v,min(list,a[i].v));

            if(p){

                list-=p;

                flow+=p;

                a[i].v-=p;

                if(i%2)

                    a[i+1].v+=p;

                else

                    a[i-1].v+=p;

                if(!list)

                    break;

            }

        }

    }

    if(!flow)

        dep[k]=-1;

    return flow;

}

inline int Dinic(int js){

    re int k;

    while(bfs()){

    for(re int i=0;i<=t;i++)

        cur[i]=head[i];

    while((k=dfs(s,inf))){

            js+=k;

        if(js>=Min)

        return js;

    }

    }

    return js;

}

struct node1 {

    int x,y,z;

}b[5010];

inline void solve(re int x){

    cnt=s=tot=maxx=0;

    re int ans=0;

    for(re int i=0;i<A;i++){

    if(x&(1<<i)) ans++,bj[i+1]=0;

    else bj[i+1]=1;

    }

    for(re int i=1;i<=res;i++)

    if(bj[b[i].x]) S[++tot]=b[i].y,ss[tot]=b[i].z;

    for(re int i=1;i<=tot;i++) maxx=max(maxx,max(S[i],ss[i]));

    t=maxx*2+1;

    for(re int i=s;i<=t;i++)

    head[i]=0;

    for(re int i=1;i<=maxx;i++)

    add(s,i,1),add(i+maxx,t,1);

    for(re int i=1;i<=tot;i++) add(S[i],ss[i]+maxx,1);

    Min=min(Min,Dinic(ans));

}

int main(){

    int D=read();

    bin[0]=1;

    for(re int i=1;i<=20;i++)

    bin[i]=bin[i-1]<<1;

    while(D--){

    A=read(),B=read(),C=read(),minx=min(A,min(B,C)),res=0,Min=inf;

    if(B==minx)

        swap(A,B);

    else if(C==minx)

        swap(A,C);

    for(re int i=1;i<=A;i++)

        for(re int j=1;j<=B;j++)

        for(re int k=1;k<=C;k++){

            x=read();

            if(x)

            b[++res].x=i,b[res].y=j,b[res].z=k;

        }

    for(re int i=0;i<bin[A];i++)

        solve(i);

    printf("%d\n",Min);

    }

}