题目大意：
给你一个(n*m) 的矩阵，问要让无线电覆盖所有的城市最少建立多少个基站，基站只能在城市上建立，并且我在一个位置建好基站之后，除了能覆盖我盖基站的位置之外还能覆盖我建立基站位置的（上下左右）任意位置的一个基站，只能从四个位置中选择一个。
题目输入：
一个T代表T组测试数据。
一个n 和 一个 m 代表 n行 m列
矩阵中包含的是 ‘*’， ‘o’,
‘*’代表一个城市，
‘o’代表空地
题目解析：和HDU 4185 Oil Skimming 这个差不多
#include<stdio.h> #include<string.h> #include<algorithm> #include<iostream> #include<vector> #include<queue> #include<cmath> using namespace std; #define INF 0x3fffffff #define maxn 605 int n, CityNum, k, m;///重构图之后顶点的个数 OilNum int Head[maxn]; int maps[maxn][maxn], P[maxn]; bool vis[maxn]; struct Node { int e, next; }edge[maxn*maxn]; void AddEdge(int s,int e) { edge[k].next = Head[s]; edge[k].e = e; Head[s] = k ++; } bool Find(int u) { for(int i=Head[u]; i != -1; i = edge[i].next) { int v = edge[i].e; if(!vis[v]) { vis[v] = true; if(P[v] == -1 || Find(P[v])) { P[v] = u; return true; } } } return false; } int solve() { int ans = 0, ans2 = 0; memset(P, -1, sizeof(P)); for(int i=1; i<=CityNum; i++) { memset(vis, false, sizeof(vis)); if(Find(i)) ans ++; else ans2 ++; } return ans / 2 + ans2; } int main() { int T, cas = 1; char str[maxn]; scanf("%d", &T); while(T--) { scanf("%d %d", &n, &m); k = CityNum = 0; memset(Head, -1, sizeof(Head)); memset(maps, 0, sizeof(maps)); for(int i=0; i<n; i++)///读入图，并且重新标记 { scanf("%s", str); for(int j=0; j<m; j++) { if(str[j] == 'o') maps[i+1][j+1] = 0; if(str[j] == '*') maps[i+1][j+1] = ++CityNum; } } for(int i=1; i<=n; i++)///重新构图 { for(int j=1; j<=m; j++) { if(maps[i][j]) { if(maps[i-1][j]) AddEdge(maps[i][j], maps[i-1][j]); if(maps[i+1][j]) AddEdge(maps[i][j], maps[i+1][j]); if(maps[i][j-1]) AddEdge(maps[i][j], maps[i][j-1]); if(maps[i][j+1]) AddEdge(maps[i][j], maps[i][j+1]); } } } printf("%d ", solve()); } return 0; } /* 3 1 0 1 1 0 1 0 1 0 */