[HNOI2013] 消毒 - 二分图匹配

容易发现 \(a,b,c\) 中至少有一个 \(\leq 17\)

不妨将其调剂为 \(a\)，那么我们可以暴力枚举哪些 \(x\) 片片要被直接削掉，剩下的拍扁成二维情况

二维时，如果有一个格子是 \(1\)，就把它的行列对应点连边，跑二分图匹配即可

好像有点卡常啊，我太难了

#include <bits/stdc++.h>

using namespace std;

#define N 255

namespace phi {

int n,m,p,cx[N],cy[N],vis[N];

std::vector<int> e[N];

int dfs(int u,int Time) {

	for(int i=0;i<(int)e[u].size();++i) {

		int v=e[u][i];

		if(vis[v]^Time) {

			vis[v]=Time;

			if(!cy[v]||dfs(cy[v],Time)) {

				cx[u]=v; cy[v]=u;

				return 1;

			}

		}

	}

	return 0;

}

void init() {

    m=p=0;

    memset(cx,0,sizeof cx);

    memset(cy,0,sizeof cy);

    memset(vis,0,sizeof vis);

	for(int i=1;i<=n;i++) e[i].clear();

}

void make(int u,int v) {

    e[u].push_back(v);

}

int solve(){

	int ans=0;

	for(int i=1;i<=n;++i) ans+=dfs(i,i);

	return ans;

}

}

int T,a,b,c,ta,tb,tc,ans=1e+9;

bool g[18][255][5005],h[255][5005];

int main() {

    scanf("%d",&T);

    while(T--){

        memset(g,0,sizeof g);

        memset(h,0,sizeof h);

        ans=1e+9;

        scanf("%d%d%d",&a,&b,&c);

        int A=a,B=b,C=c;

        ta=1; tb=2; tc=3;

        if(a>b) swap(a,b), swap(ta,tb);

        if(a>c) swap(a,c), swap(ta,tc);

        if(b>c) swap(b,c), swap(tb,tc);

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

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

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

                    int t;

                    cin>>t;

                    int x=i,y=j,z=k;

                    if(A>B) swap(x,y);

                    if(A>C) swap(x,z);

                    if(B>C) swap(y,z);

                    g[x][y][z]=t;

                }

            }

        }

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

            if(__builtin_popcount(i)>=ans) continue;

            int u[20]={};

            for(int p=1;p<=B;p++) {

                for(int q=1;q<=C;q++) {

                    h[p][q]=0;

                }

            }

            for(int j=1;j<=A;j++) {

                u[j]=(i>>(j-1))&1;

                if(u[j]==0) {

                    for(int p=1;p<=B;p++) {

                        for(int q=1;q<=C;q++) {

                            h[p][q]|=g[j][p][q];

                        }

                    }

                }

            }

            phi::n=B;

            phi::init();

            for(int p=1;p<=B;p++) {

                for(int q=1;q<=C;q++) {

                    if(h[p][q]) phi::make(p,q);

                }

            }

            int tmp=phi::solve()+__builtin_popcount(i);

            ans=min(ans,tmp);

        }

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

    }

}

巴特西

[HNOI2013] 消毒 - 二分图匹配

最新文章

热门文章