UVA10349 Antenna Placement

题意

一个矩形中，有n个城市’*’，现在这n个城市都要覆盖无线，若放置一个基站，那么它至多可以覆盖相邻的两个城市。 问至少放置多少个基站才能使得所有的城市都覆盖无线？

分析

每一个城市都需要被一个基站覆盖，而一个基站最多覆盖两个城市。为了使基站的数量最少，我们可以考虑让尽可能多的基站覆盖两个城市。设最多能让a个基站覆盖两个城市，则一共需要 n-a个基站。问题转化为求这个a。这种覆盖方式是不是似曾相识？对了，就是二分图！对于每个矩阵中的点(i,j)，若(i+j)&1 == 1 ，则涂成黑色，反之涂成白色。这样一来，对于每个矩阵中相邻的点，都是黑白形式，也就是说，都是涂成黑色的点连向涂成白色的点。到这一步，恭喜您成功获得二分图模型，这不就是求二分图的最大配对吗？不会二分图的请移步模板。

CODE

#include
#include
#include
#include<string>
#include
#include
#include
#include
using namespace std;
#define N 45
#define M N*N
int H,W,k,tot,ans,cnt;
int head[M],Next[M],ver[M];
int match[M],vis[M],v[N][N];
bool flag[M];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
void add(int x,int y){
    ver[++tot]=y;
    Next[tot]=head[x],head[x]=tot;
}
char c[N][N];
bool dfs(int x){
    for(int i=head[x],y;i;i=Next[i])
        if(!vis[y=ver[i]]){
            vis[y]=1;
            if(!match[y]||dfs(match[y])){
                match[y]=x;
                return true;
            }
        }
    return false;
}//匈牙利板子 
void init(){
    ans=tot=cnt=0;
    memset(head,0,sizeof(head));
    memset(flag,0,sizeof(flag));
    memset(v,0,sizeof(v));
    memset(match,0,sizeof(match));
}//极其重要的清零 
int t;
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&H,&W);
        init();
        for(int i=1;i<=H;++i)
            for(int j=1;j<=W;++j){
                scanf(" %c",&c[i][j]);
                if(c[i][j]=='*') {
                    v[i][j]=++cnt; 
                    if((i+j)&1) flag[cnt]=1; //将黑色的点区别出来 
                }
            }
        for(int i=1;i<=H;++i)
            for(int j=1;j<=W;++j)
                if(v[i][j]){
                    for(int k=0;k<4;++k){
                        int x=i+dx[k],y=j+dy[k];
                        if(v[x][y]) add(v[i][j],v[x][y]); 
                    }//四个方向都要看 
                }
        for(int i=1;i<=cnt;++i){
            if(!flag[i]) continue;
            memset(vis,0,sizeof(vis));
            if(dfs(i)) ++ans;
        }
        printf("%d\n",cnt-ans);
    }
    return 0;
}
二分图

相关

【算法笔记】二分图与KM算法（当你试图只看蓝书学算法

二分图的最大匹配、完美匹配和匈牙利算法

Leetcode 785. 判断二分图（中等）& 886. 可能的二分法（中等） 二分图判断

二分图总结

二分图

二分图的最大匹配

网络流，二分图与图的匹配

标签