题目链接
题意
给定一个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;
}