[BZOJ3140/Luogu3231][Hnoi2013]消毒(二分图)

发布于 2018-02-11  56 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3140/Luogu3231][Hnoi2013]消毒(二分图)

Description

最近在生物实验室工作的小T遇到了大麻烦。
由于实验室最近升级的缘故,他的分格实验皿是一个长方体,其尺寸为a*b*c,a、b、c 均为正整数。为了实验的方便,它被划分为a*b*c个单位立方体区域,每个单位立方体尺寸为1*1*1。用(i,j,k)标识一个单位立方体,1 ≤i≤a,1≤j≤b,1≤k≤c。这个实验皿已经很久没有人用了,现在,小T被导师要求将其中一些单位立方体区域进 行消毒操作(每个区域可以被重复消毒)。而由于严格的实验要求,他被要求使用一种特定 的F试剂来进行消毒。 这种F试剂特别奇怪,每次对尺寸为x*y*z的长方体区域(它由x*y*z个单位立方体组 成)进行消毒时,只需要使用min{x,y,z}单位的F试剂。F试剂的价格不菲,这可难倒了小 T。现在请你告诉他,最少要用多少单位的F试剂。(注:min{x,y,z}表示x、y、z中的最小 者。)

Http

BZOJ
Luogu

Tag

二分图

解决思路

首先要知道,不需要消毒的地方也是可以消毒的!这是前提。
考虑如果某一维我们取\(1\),那么剩下的两维取最大是最优的,那么也就是说我们可以一次消毒一层。
那么如果是两维,根据上面的贪心,我们每一次消掉一行或一列是最优的,那么这就变成了选择若干行或若干列使得所有需要消毒的格子都被包含进去。把行和列分别看作两个集合,对于需要消毒的格子\(x,y\),从行的\(x\)连边到\(y\),求最小点覆盖,即选出最少的点使得所有的边都至少有一个端点在点集中。在二分图中,最小点覆盖\(=\)最大匹配。所以对于二维的,直接匈牙利算法求解最大匹配。
但现在是三维,那么会出现的情况就是某几层可能是直接一层一层消去的,考虑到\(a*b*c\)最多只有\(5000\),也就是说这三个数中最小的不会超过\(17\),那么可以枚举最小这一维,枚举其中每一层是直接一层地消毒还是用另外两维来消。直接消的就统计层数即可,剩下的由于我们上面的贪心原则,可以把剩下的所有面全部压缩到一个平面上,这样就变成二维的情况了,运用匈牙利算法解决。
注意在应该\(continue\)的地方都要可行性剪枝。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;

#define ll long long
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=6000;
const int maxM=maxN*2;
const int inf=2147483647;

class Pos
{
public:
    int x,y,z;
};

int a,b,c,nodecnt,nowdepth=0;
int edgecnt=0,Head[maxN],Next[maxM],V[maxM];
int vis[maxN],Match[maxN];
Pos P[maxN];

void Add_Edge(int u,int v);
int dfs(int u);

int main()
{
    int T;scanf("%d",&T);
    while (T--)
    {
        nodecnt=0;
        scanf("%d%d%d",&a,&b,&c);
        for (int i=1;i<=a;i++) for (int j=1;j<=b;j++) for (int k=1;k<=c;k++)
                                                      {
                                                          int opt;scanf("%d",&opt);
                                                          if (opt==1) P[++nodecnt]=(Pos){i,j,k};
                                                      }
        //这里是为了保证a<b<c,方便后面的枚举
        if (a>b){
            swap(a,b);for (int i=1;i<=nodecnt;i++) swap(P[i].x,P[i].y);
        }
        if (a>c){
            swap(a,c);for (int i=1;i<=nodecnt;i++) swap(P[i].x,P[i].z);
        }
        if (b>c){
            swap(b,c);for (int i=1;i<=nodecnt;i++) swap(P[i].y,P[i].z);
        }
        int Ans=inf;
        for (int S=0;S<(1<<a);S++)//枚举哪些层直接整层消毒
        {
            edgecnt=0;for (int i=1;i<=c;i++) Head[i]=Match[i]=-1;
            int ret=0;
            for (int i=1;i<=a;i++) if ((S&(1<<(i-1)))!=0) ret++;//直接消毒的,每一层的代价都是1
            if (ret>=Ans) continue;
            for (int i=1;i<=nodecnt;i++) if ((S&(1<<(P[i].x-1)))==0) Add_Edge(P[i].y,P[i].z);//建二分图
            for (int i=1;i<=c;i++)//匈牙利算法
            {
                nowdepth++;
                ret+=dfs(i);
                if (ret>=Ans) break;
            }
            Ans=min(Ans,ret);
        }
        printf("%d\n",Ans);
    }
    return 0;
}

int dfs(int u)
{
    for (int i=Head[u];i!=-1;i=Next[i])
        if (vis[V[i]]!=nowdepth)
        {
            vis[V[i]]=nowdepth;
            if ((Match[V[i]]==-1)||(dfs(Match[V[i]])))
            {
                Match[V[i]]=u;return 1;
            }
        }
    return 0;
}

void Add_Edge(int u,int v)
{
    edgecnt++;Next[edgecnt]=Head[u];Head[u]=edgecnt;V[edgecnt]=v;
    return;
}

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3140/Luogu3231][Hnoi2013]消毒(二分图)


HNCJ OIer