题目链接
Antenna Placement POJ - 3020
题意
给定一个n*m的字符矩阵，‘o’表示空地，’*‘表示城市。现要在城市建立基站，使得所有的城市都有信号。每个基站只能覆盖两个相邻点（包括基站建立点在内）。求最少的基站数。
分析
将城市作为点集，相邻城市连边，如此构建一个图。这个图可以看作一个二分图，这样，这就是一个最小边覆盖问题。根据结论“最小边覆盖=顶点数-最大匹配”，我们只要求出二分图的最大匹配即可。
根据字符矩阵得到图，然后我们可以通过染色去确定二分图的X集和Y集。也可以将所有点看作X’集，所有点复制一份看作Y‘集，这样得到的最大匹配就是原图的最大匹配的两倍。
看到网上有些博客说这是最小路径覆盖问题，我不是很明白，因为我觉得这就是一个裸的最小边覆盖问题。
解释下为什么：
最小边覆盖的定义是“选最少的边使得每个点都和所选边关联”。
将基地抽象成边，城市抽象成点。一个基地覆盖两个城市，可以抽象成一条边关联两个点。这样，选最少的基地就等价于“选最少的边使得每个点都和所选边关联”。这和最小边覆盖的定义是吻合的。
而最小路径覆盖的定义是“用尽量少的不相交的简单路径覆盖有向无环图G的所有结点”。我不太明白怎么去将基地抽象成路径。
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;const int maxn=500;
vector<int> g[maxn],X;
int from[maxn],used[maxn];
int cnt,n,m,hash[44][12];
char s[44][12];
int dir[4][2]={
0,1,0,-1,1,0,-1,0};bool valid(int x,int y)
{return s[x][y]=='*' && x>=0&&x<n && y>=0&&y<m;
}
bool Find(int u)
{for(int i=0;i<g[u].size();i++){int v=g[u][i];if(!used[v]){used[v]=1;if(from[v]==-1 || Find(from[v])){from[v]=u;return true;}}}return false;
}
void solve()
{int ans=0;memset(from,-1,sizeof(from));for(int i=1;i<=cnt;i++){memset(used,0,sizeof(used));if(Find(i)) ans++;}printf("%d\n",cnt-ans/2);
}
int main()
{int T;scanf("%d",&T);while(T--){cnt=0;scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%s",s[i]);for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(s[i][j]=='*')hash[i][j]=++cnt;for(int i=0;i<n;i++)for(int j=0;j<m;j++){if(s[i][j]=='*'){for(int k=0;k<4;k++){int fi=i+dir[k][0];int fj=j+dir[k][1];if(valid(fi,fj))g[hash[i][j]].push_back(hash[fi][fj]);}}}solve();for(int i=0;i<=cnt;i++) g[i].clear();}return 0;
}参考博客
模板总结——二分图最大匹配