题目链接：
?id=3020
题目大意：
在N*M的矩阵中，有K个城市要覆盖无线网。而一个无线网基站只能覆盖左右相邻或是上下相邻的两个
城市。问：至少放置多少个基站，能将这K个城市全部覆盖。输入数据时，’*’表示城市，’o’表示空地。
思路：
K个城市作为K个点，，编号为1~K。如果有两个城市相邻，则两个城市之间建立一条双向边。现在问题
变为了怎么从图中选择最少的边，使得能够覆盖所有的点。可以用二分图最小边覆盖来做。首先遍历
原图，对K个城市编号，存入iMap[][]数组中。然后建立一个二分图，两边都为K个城市。如果两个城
市有边(即两个城市相邻)，则将边加入二分图中。由于二分图最小边覆盖 = K+K – 二分图最大匹配。
这里是无向图，匹配和点都重复计算了两次。所以结果 = K – 二分图最大匹配/2。这道题小懮博客上
写的非常好，可以参考一下：
AC代码：
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>using namespace std;const int MAXN = 440;bool Map[MAXN][MAXN],Mask[MAXN];int NX,NY;int cx[MAXN],cy[MAXN];int DireR[4] = {0,0,1,-1};int DireC[4] = {1,-1,0,0};int iMap[MAXN][MAXN];char G[44][11];int FindPath(int u){for(int i = 1; i <= NY; ++i){if(Map[u][i] && !Mask[i]){Mask[i] = 1;if(cy[i] == -1 || FindPath(cy[i])){cy[i] = u;cx[u] = i;return 1;}}}return 0;}int MaxMatch(){for(int i = 1; i <= NX; ++i)cx[i] = -1;for(int i = 1; i <= NY; ++i)cy[i] = -1;int res = 0;for(int i = 1; i <= NX; ++i){if(cx[i] == -1){for(int j = 1; j <= NY; ++j)Mask[j] = 0;res += FindPath(i);}}return res;}int main(){int T,N,M,id;scanf("%d",&T);while(T–){id = 1;scanf("%d%d",&N,&M);memset(iMap,0,sizeof(iMap));memset(Map,0,sizeof(Map));for(int i = 1; i <= N; ++i){getchar();for(int j = 1; j <= M; ++j){scanf("%c",&G[i][j]);if(G[i][j] == '*')iMap[i][j] = id++;}}for(int i = 1; i <= N; ++i){for(int j = 1; j <= M; ++j){if(iMap[i][j]){for(int k = 0; k < 4; ++k){int x = i + DireR[k];int y = j + DireC[k];if(iMap[x][y])Map[iMap[i][j]][iMap[x][y]] = 1;}}}}NX = NY = id-1;printf("%d\n",id-1-MaxMatch()/2);}return 0;}
自己打败自己的远远多于比别人打败的。
