POJ3020 最小边覆盖（匈牙利算法）

不念不忘少年蓝@ 2022-05-17 11:41 197阅读 0赞

题目链接：  
[POJ3020][]

题目大意：在一个网格中，给定特殊点的位置，问你最少需要多少个信号塔（只能上下左右选择其中一个分析覆盖两个特殊点）才能覆盖所有的特殊点。

解题思路：  
一开始博主看到这题，觉得一发遍历就可以得出答案，接过提交WA了，后面才想到如果出现这样的情况  
![这里写图片描述][70]  
，遍历就是错误的。遍历需要3个信号塔覆盖，而正确应该是2个信号塔就可以覆盖。

因此，毕竟知道是二分图匹配专题，所以需要回到原点，如何和二分图匹配联系在一起呢？？

我们知道二分图匹配需要两个点集，那我们是否可以将\*点抽象出来1，2，3，这样的数字点，然后建立起图，比如1和2属于相邻关系的画，就建立一条无向边在1,2之间。

这样我们就可以利用匈牙利算法求出最大二分匹配数  
而我们知道:

## 无向二分图的最小边覆盖 = 顶点数 – 最大二分匹配数/2 ##

顶点数：就是用于构造无向二分图的城市数，即\*的数量

最大二分匹配书之所以要除以2，是因为无向图匹配是双向的，因此除以2得到原图的真正的匹配数

这里可以参考博主觉得讲得特别好的一个博主：  
[穿梭门][Link 1]

这样我们先根据输出，把图建好，然后利用匈牙利算法求出最大二分匹配数  
然后答案就出来了！！！

AC代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    using namespace std;
    
    
    char a[45][15];
    int g[405][405],vis[405],temp[45][15],f[405];
    int h,w,n,ans,cnt;
    
    void buildGraph(){
        cnt=0;
        for(int i=0; i<h; ++i){
           for(int j=0; j<w; ++j){
                if(a[i][j]=='*') temp[i][j] = ++cnt;
                else temp[i][j] = 0;
            }
        }
        int r=h, c=w;
        for(int i=0; i<h; ++i){
            for(int j=0; j<w; ++j){
                if(temp[i][j]!=0){
                    if(i-1>=0&&temp[i-1][j]!=0){
                        g[temp[i][j]][temp[i-1][j]]=1;
                    }
                    if(i+1<r&&temp[i+1][j]!=0){
                        g[temp[i][j]][temp[i+1][j]]=1;
                    }
                    if(j-1>=0&&temp[i][j-1]!=0){
                        g[temp[i][j]][temp[i][j-1]]=1;
                    }
                    if(j+1<c&&temp[i][j+1]!=0){
                        g[temp[i][j]][temp[i][j+1]]=1;
                    }
                }
            }
        }
    
    }
    
    bool find(int x){
        for(int j=1; j<=cnt; ++j){
            if(g[x][j]&&!vis[j]){
                vis[j]=1;
                if(f[j]==0 || find(f[j])){
                    f[j]=x;
                    return true;
                }
            }
        }
        return false;
    }
    
    void init(){
        memset(g, 0, sizeof(g));
        memset(temp, 0, sizeof(temp));
        memset(f, 0, sizeof(f));
        ans=0;
    }
    
    int main(int argc, char const *argv[])
    {
        scanf("%d",&n);
        while(n--){
            init();
            scanf("%d%d",&h,&w);
            for(int i=0; i<h; ++i) scanf("%s",a[i]);
            buildGraph();
    
            int ret=0;
            for(int i=1; i<=cnt; ++i){
                memset(vis,0,sizeof(vis));
                if(find(i)) ret++;
            }
         //   cout<<ret<<endl;
            ans=cnt-ret/2;
            printf("%d\n",ans);
        }
        return 0;
    }

[POJ3020]: http://poj.org/problem?id=3020
[70]: /images/20220517/e51b21ded7c847ffbc7ebf558f1b3fe5.png
[Link 1]: https://blog.csdn.net/lyy289065406/article/details/6647040