题意：
一个矩形中，有N个城市’*’，现在这n个城市都要覆盖无线，若放置一个基站，那么它至多可以覆盖相邻的两个城市。
问至少放置多少个基站才能使得所有的城市都覆盖无线？
思路：
给每个城市编号，建双向边，跑匈牙利，然后城市数量-匹配数/2就是答案
因为假设每个城市都要建基站，然后有多少个匹配就减少多少个基站，由于是双向边所以要/2
/* *********************************************** Author :devil Created Time :2016/5/17 11:25:49 ************************************************ */ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <cmath> #include <stdlib.h> using namespace std; char s[42][12]; int mp[42][12],link[410]; bool vis[410]; vector<int>eg[410]; bool dfs(int u) { for(int i=0;i<eg[u].size();i++) { int v=eg[u][i]; if(!vis[v]) { vis[v]=1; if(link[v]==-1||dfs(link[v])) { link[v]=u; return 1; } } } return 0; } int main() { //freopen("in.txt","r",stdin); int t; scanf("%d",&t); while(t--) { int n,m,cnt=0; memset(link,-1,sizeof(link)); 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]=='*') mp[i][j]=++cnt; for(int i=1;i<=cnt;i++) eg[i].clear(); for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { if(s[i][j]=='*') { if(i<n-1&&s[i+1][j]=='*') { eg[mp[i][j]].push_back(mp[i+1][j]); eg[mp[i+1][j]].push_back(mp[i][j]); } if(j<m-1&&s[i][j+1]=='*') { eg[mp[i][j]].push_back(mp[i][j+1]); eg[mp[i][j+1]].push_back(mp[i][j]); } } } } int ans=0; for(int i=1;i<=cnt;i++) { memset(vis,0,sizeof(vis)); ans+=dfs(i); } printf("%d ",cnt-ans/2); } return 0; }