匈牙利算法+最小点覆盖最佳入门题 UVA-11419

Love The Way You Lie 2022-05-24 08:26 148阅读 0赞

*  题目链接
    
    [SAM I AM][]

题目大意：  
在给定r\*c的网格中，给出敌人在网格里的位置，你有一个武器，一发炮弹可以打死一行或一列的所有敌人。求出最少的炮弹数可以把所有敌人干掉，并且输出每次发射炮弹的位置

题解：  
这个题典型符合二分图最大匹配问题，以网格的行作为x,列作为y,敌人的位置作为边（如敌人位置为（1，2），则x中1与y中2应该连一条边）。接着用匈牙利算法最大匹配数M，即使用的最少炮弹数。对于要求出每次发射炮弹的位置，则需要用到最小点覆盖König定理的简单证明步骤反推回去）。具体看代码，有解释  
求最小点覆盖，可参考这两幅图  
![这里写图片描述][70]![这里写图片描述][70 1]

AC代码：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    const int MAXN=1005;
    bool map[MAXN][MAXN];
    bool visited[MAXN];
    int link[MAXN],antilink[MAXN]; //antilink记录x和谁匹配了，用于之后找增广路，便于标记
    bool flagx[MAXN],flagy[MAXN];  //用于记录哪些点被标记了
    int r,c,n,ans;
    //经典匈牙利算法
    bool dfs(int x){
        for(int i=1;i<=c;++i){
            if(map[x][i]&&!visited[i]){
                visited[i]=1;
                if(link[i]==0||dfs(link[i])){
                    link[i]=x;
                    antilink[x]=i;
                    return true;
                }
            }
        }
        return false;
    }
    
    void search(){
        for(int i=1;i<=r;++i){
            memset(visited,0,sizeof(visited));
            if(dfs(i)) ans++;
        }
    }
    //求最小点覆盖是哪些点
    void Minpoints(int y){
        flagy[y]=1;  //标记y侧的点
        for(int i=1;i<=r;++i){
            if(map[i][y]&&!visited[i]){
                flagx[i]=1;  //标记路上经过x侧的点
                visited[i]=1;
                if(antilink[i]==0) return; //无路可走了
                Minpoints(antilink[i]); //不断走下去
            }
        }
        return ;
    }
    int main(){
        while(scanf("%d%d%d",&r,&c,&n)!=EOF){
            memset(map,0,sizeof(map));
            memset(link,0,sizeof(link));
            memset(antilink,0,sizeof(antilink));
            memset(flagx,0,sizeof(flagx));
            memset(flagy,0,sizeof(flagy));
            ans=0;
            for(int i=0;i<n;++i){
                int x,y;
                scanf("%d%d",&x,&y);
                map[x][y]=1;
            }
            search();
            //从y侧每个没有被匹配的点作为起始开始找增广路
            for(int j=1;j<=c;++j){
                memset(visited,0,sizeof(visited));
                if(link[j]==0){
                    Minpoints(j);
                }
            }
            cout<<ans<<" ";
            //右边没有打上记号的点，加上左边已经有记号的点组成了最小覆盖点集
            for(int j=1;j<=c;++j){
                if(flagy[j]==0)cout<<"c"<<j<<" ";
            }
            for(int i=1;i<=r;++i){
                if(flagx[i]==1)cout<<"r"<<i<<" ";
            }
            cout<<endl;
        }
        return 0;
    }

[SAM I AM]: https://vjudge.net/problem/UVA-11419
[70]: https://img-blog.csdn.net/20180523102646953?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTcyNTA1/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 1]: /images/20220524/a8cbd6c6937d475f93471d9aeaab4c1c.png