题目链接：http://poj.org/problem?id=3020
题目大意：读入一张地图。其中地图中圈圈代表可以布置卫星的空地。*号代表要覆盖的建筑物。一个卫星的覆盖范围是其周围上下左右四个点。问最少需要几个卫星才能覆盖所有建筑物。
解题思路：
有点类似POJ 1328的覆盖题，不过那题比较简单可以贪心。这题你可以YY试试。
覆盖问题其实可以用图论解决。这题就属于最小路径覆盖，手动由一个点出发连一些路径，这样Hungry就能求出最少需要多少这样的中心点，就可以达成目标了。
本题最大的疑问是到底是建有向图，还是无向图。由于Hungry只适用于有向图，所以好像应该建有向图。但是扫描这个图的时候，Hash图上点不算简单，需要对n*m标个号，然后Hash。
建无向图其实也不是很简单，需要拆点，模拟出所谓的“有向图”来Hungry，本点放在X集，影子点放在Y集，如果有边（u，v），则u连v'(本点连影子点），对邻接矩阵每个城市相邻四个点扫一下加下边，这样自动模拟出"有向图"。
跑一遍Hungry，ans=建筑物数-match/2。（无向图match是两倍）
#include "iostream"
#include "cstdio"
#include "cstring"
#include "string"
#include "fstream"
using namespace std;
int G[][],link[];
int map[][];
bool vis[];
int Case,n,m,pos;
void AddEdge(int x,int y)
{
G[x][y]=; //本点连影子点
}
bool dfs(int u)
{
for(int v=;v<=pos;v++)
{
if(G[u][v]&&!vis[v])
{
vis[v]=true;
if(!link[v]||dfs(link[v]))
{
link[v]=u;
return true;
}
}
}
return false;
}
int main()
{
#define fin cin
ifstream fin("in.txt");
string line;
cin>>Case;
while(Case--)
{
pos=;
int res=;
cin>>n>>m;
getline(cin,line);
for(int i=;i<=n;i++) //吸收残留
{
getline(cin,line);
for(int j=;j<line.size();j++)
if(line[j]=='*') map[i][j+]=++pos;
}
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
if(map[i][j]&&map[i-][j]) AddEdge(map[i][j],map[i-][j]);
if(map[i][j]&&map[i+][j]) AddEdge(map[i][j],map[i+][j]);
if(map[i][j]&&map[i][j-]) AddEdge(map[i][j],map[i][j-]);
if(map[i][j]&&map[i][j+]) AddEdge(map[i][j],map[i][j+]);
}
}
for(int i=;i<=pos;i++)
{
memset(vis,,sizeof(vis));
if(dfs(i)) res++;
}
res=pos-res/;
cout<<res<<endl;
memset(map,,sizeof(map));
memset(G,,sizeof(G));
memset(link,,sizeof(link));
}
}