HNOI2013 消毒

水深无声 2021-10-30 01:22 237阅读 0赞

### 题目链接：[戳我][Link 1] ###

开始有一种错误的想法，那就是最小割，我们给三个维度上的每个点都拆成两个，然后中间连流量为1的边，之后如果一个点在\\((x,y,z)\\)，那么我们就连接\\((x,y+2\*n,z+4\*n)\\)，然后跑一遍dinic求最小割。这个想法甚至作为了[luogu小行星][luogu]这道题的std emmmm（所以那个题假掉了）

为什么假掉了？可以试一试这组数据：  
4  
1 1 2  
1 2 1  
2 1 3  
3 3 3  
正确的输出应该是2，但是题解们输出的都是3。

为什么会大呢？

这是因为最小割一定会拓展到原图彻底两边不连通为止，但是你割掉一部分边之后，可能还存在一些联通的路径。但是如果这时候存在的联通路径是不合法的（即没有一颗小行星在这条路径表示的点的位置上），那么其实这是不用割掉的。但是按照最小割，你不得不继续拓展下去，导致答案的增加。

如果是一个二维平面，想必大家都会做，因为覆盖掉一个x\*y的矩形，只需要\\(min(x,y)\\)的代价就可以完全覆盖掉它。我们把长宽分开，当做二分图，如果一个位置（比如说\\((x,y)\\)），我们连接一条有向边x,y即可。然后最小点覆盖就可以了。

因为\\(a\*b\*c\\le 5000\\)，所以必定有一维小于等于17.

因为最小点覆盖等于二分图最大匹配，所以我们使用匈牙利算法算二分图匹配即可；

代码如下：

#include<iostream>
    #include<cmath>
    #include<cstring>
    #include<algorithm>
    #include<cmath>
    #define MAXN 5010
    using namespace std;
    int T,a,b,c,t,tot,ans;
    int head[MAXN],kkk[4][MAXN],flag[MAXN],done[MAXN],color[MAXN];
    struct Edge{int nxt,to;}edge[MAXN<<1];
    inline void add(int from,int to){edge[++t].nxt=head[from],edge[t].to=to,head[from]=t;}
    inline bool dfs(int x)
    {
        for(int i=head[x];i;i=edge[i].nxt)
        {
            int v=edge[i].to;
            if(!done[v])
            {
                done[v]=1;
                if(!color[v]||dfs(color[v]))
                {
                    color[v]=x;
                    return true;
                }
            }
        }
        return false;
    }
    inline void solve(int x)
    {
        memset(head,0,sizeof(head));
        memset(color,0,sizeof(color));
        t=0;
        int cur_ans=0;
        for(int i=0;i<a;i++)
        {
            if(x&(1<<i)) flag[i+1]=false,cur_ans++;
            else flag[i+1]=true;
        }
        for(int i=1;i<=tot;i++)
            if(flag[kkk[1][i]]==true)
                add(kkk[2][i],kkk[3][i]);
        for(int i=1;i<=b;i++)
        {
            for(int j=1;j<=c;j++) done[j]=0;
            if(dfs(i)) cur_ans++;
        }
        ans=min(ans,cur_ans);
    }
    int main()
    {
        #ifndef ONLINE_JUDGE
        freopen("ce.in","r",stdin);
        #endif
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d%d%d",&a,&b,&c);
            ans=0x3f3f3f3f,tot=0;
            int minn=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++)
                    {
                        int cur;
                        scanf("%d",&cur);
                        if(cur==0) continue;
                        kkk[1][++tot]=i,kkk[2][tot]=j,kkk[3][tot]=k;
                    }
            if(minn==b) swap(a,b),swap(kkk[1],kkk[2]);
            else if(minn==c) swap(a,c),swap(kkk[1],kkk[3]);
            for(int i=0;i<(1<<a);i++) solve(i);//printf("ans=%d\n",ans);
            printf("%d\n",ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/fengxunling/p/10805343.html

[Link 1]: https://www.luogu.org/problemnew/show/P3231
[luogu]: https://www.luogu.org/problemnew/show/P2711